Minimum Number of Taps to Open to Water a Garden
There is a one-dimensional garden on the x-axis from point 0 to point n. There are n + 1 taps, one at every integer point from 0 to n. If you open tap i, it waters the range [i - rangesi, i + rangesi]. Return the minimum number of taps that must be opened to water the full garden [0, n], or -1 if it cannot be done. Convert every tap into the farthest right point it can reach from each left starting point, then run the same greedy reachability sweep used in the jump game: extend as far as possible before opening the next tap.
Constraints
- 1 ≤ n ≤ 104
- ranges.length == n + 1
- 0 ≤ rangesi ≤ 100
Example
n = 5, ranges = [3, 4, 1, 1, 0, 1]1Explanation Opening tap 1 alone waters [max(0, 1-4), min(5, 1+4)] = [0, 5], the entire garden.
In plain terms
- Tap range
- How far a tap waters on either side of its position — a tap at position 4 with range 2 waters from 2 to 6.
Sweep the farthest-reach array like a jump game
i=0: this is the first tap decision, currentEnd is also 0. nextEnd starts at farthest[0]=5.
What happens in this step
i = 0, currentEnd = 0, taps = 0 nextEnd = max(nextEnd, farthest[0]) = max(0, 5) = 5 Scanning position i=0, the locally best reach available right now is farthest[0]=5, so nextEnd updates to 5. taps is still 0 — whether a tap actually gets "opened" is decided at the boundary check next.
Steps to visualize
- For every tap i, compute the leftmost point it can reach and record the rightmost point reachable starting from there.
- Sweep left to right, tracking the farthest point reachable so far.
- Whenever you reach the current tap boundary, "open" the next tap that extends the farthest — that is one tap used.
- If the reach ever stalls without covering more ground, the garden cannot be fully watered.
- Once the reachable point covers the full garden, return the number of taps opened.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
i=0: this is the first tap decision, currentEnd is also 0. nextEnd starts at farthest[0]=5.
What happens in this step
i = 0, currentEnd = 0, taps = 0 nextEnd = max(nextEnd, farthest[0]) = max(0, 5) = 5 Scanning position i=0, the locally best reach available right now is farthest[0]=5, so nextEnd updates to 5. taps is still 0 — whether a tap actually gets "opened" is decided at the boundary check next.
Solution
function minTaps(n, ranges) {
const farthest = new Array(n + 1).fill(0);
for (let i = 0; i <= n; i++) {
const left = Math.max(0, i - ranges[i]);
const right = Math.min(n, i + ranges[i]);
farthest[left] = Math.max(farthest[left], right);
}
let taps = 0;
let currentEnd = 0;
let nextEnd = 0;
for (let i = 0; i < n; i++) {
nextEnd = Math.max(nextEnd, farthest[i]);
if (i === currentEnd) {
if (nextEnd === i) return -1;
taps++;
currentEnd = nextEnd;
if (currentEnd >= n) return taps;
}
}
return currentEnd >= n ? taps : -1;
}- Time
- O(n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 5, ranges = [3, 4, 1, 1, 0, 1] | 1 | example from the docstring |
n = 3, ranges = [0, 0, 0, 0] | -1 | every tap has zero range, nothing gets watered beyond single points |
n = 7, ranges = [1, 2, 1, 0, 2, 1, 0, 1] | 3 | requires chaining several taps together to cover the full garden |
n = 1, ranges = [1, 1] | 1 | smallest garden, a single tap covers it entirely |
n = 2, ranges = [0, 0, 0] | -1 | larger garden with zero-range taps, impossible to water |
n = 4, ranges = [4, 0, 0, 0, 0] | 1 | a single wide tap at the start covers the whole garden |
n = 3, ranges = [1, 0, 0, 0] | -1 | coverage stalls partway through, leaving a gap that cannot be watered |