Minimum Number of Taps to Open to Water a Garden: Greedy Interval Covering
There is a one-dimensional garden on the x-axis from point 0 to point n. You have n + 1 taps located at points 0, 1, 2, ..., n. Given an integer n and an array ranges of length n + 1 where ranges[i] is the range that tap i can water (it waters the interval [i - ranges[i], i + ranges[i]]), return the minimum number of taps that need to be open to water the whole garden [0, n]. If the garden cannot be watered, return -1.
This is LeetCode 1326: Minimum Number of Taps to Open to Water a Garden.
Why this problem matters
At first glance this looks like a specialized geometry problem, but it is actually a classic interval covering problem in disguise. Once you convert each tap into its coverage interval, you are asking: what is the minimum number of intervals needed to cover [0, n]? This is the same structure as Video Stitching (LeetCode 1024) and reduces directly to Jump Game II (LeetCode 45).
Recognizing this reduction is the real skill. Many hard problems become medium or even easy once you see they are instances of a known pattern. Interval covering with greedy farthest-reach is one of those patterns that shows up repeatedly across different problem skins.
The key insight
Each tap at position i with range ranges[i] covers the interval [i - ranges[i], i + ranges[i]]. Once you have all these intervals, you want to cover [0, n] with as few as possible. The trick is to transform the intervals into a "max reach from each start position" array, then apply the Jump Game II greedy algorithm.
For each interval [left, right], you record that from position left you can reach at least right. Store this in maxReach[left] = max(maxReach[left], right). Now scan from left to right, greedily jumping to the farthest point reachable from your current range. Each jump costs one tap.
The solution
def minTaps(n, ranges):
max_reach = [0] * (n + 1)
for i, r in enumerate(ranges):
left = max(0, i - r)
right = min(n, i + r)
max_reach[left] = max(max_reach[left], right)
taps = 0
end = 0
farthest = 0
for i in range(n):
farthest = max(farthest, max_reach[i])
if farthest <= i:
return -1
if i == end:
taps += 1
end = farthest
return taps
The first loop converts taps to intervals and builds the max_reach array. The second loop is the Jump Game II greedy scan: track the current boundary (end) and the farthest point reachable (farthest). When you hit the boundary, take a new jump (open another tap) and extend the boundary to farthest. If at any point farthest cannot get past position i, the garden is impossible to water.
The reduction to Jump Game II is the entire insight. Once you build max_reach, the remaining code is identical to Jump Game II with one extra check: if farthest never moves past your current position, return -1.
Visual walkthrough
Step 1: Convert each tap to an interval [i - ranges[i], i + ranges[i]]
Each tap covers a symmetric range. Clamp left to 0 and right to n.
Step 2: Build maxReach[i] = farthest right endpoint from position i
For each interval [left, right], update maxReach[left] = max(maxReach[left], right). This reduces the problem to Jump Game II.
Step 3: Greedy farthest-reach (Jump Game II). Start at 0, jump to farthest.
At position 0, maxReach[0] = 5 which covers the entire garden. One jump suffices.
Step 4: Another example. ranges = [0, 0, 1, 1, 2, 1], maxReach = [0, 0, 3, 4, 5, 5]
No single tap covers [0, 5]. The algorithm needs at least 2 jumps, but position 0 has reach 0 so it returns -1 (impossible).
In the first example (ranges = [3, 4, 1, 1, 0, 0]), tap 1 alone covers [-3, 5] which, clamped to the garden, means [0, 5]. So a single tap suffices. The greedy algorithm discovers this immediately: at position 0, maxReach[0] = 5 already covers the entire garden. One jump, one tap, done.
The second example shows what happens when no tap covers position 0. The maxReach[0] = 0 means you cannot move past the starting point, so the algorithm returns -1 immediately.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Greedy (Jump Game reduction) | O(n) | O(n) |
Time: O(n). Two linear passes. The first pass builds max_reach in O(n). The second pass scans from 0 to n-1 in O(n). Each iteration does O(1) work.
Space: O(n). The max_reach array has n+1 entries. No recursion, no sorting, no priority queue.
A dynamic programming approach also solves this problem in O(n^2) time and O(n) space by computing the minimum taps to reach each position. The greedy approach is strictly better because it exploits the same structure as Jump Game II to achieve linear time.
The building blocks
1. Interval representation
The first step is recognizing that each tap defines an interval and converting the tap parameters into standard [left, right] form. This is a common preprocessing step in interval problems. Once you have intervals, you can apply known interval algorithms (merge, sweep line, greedy cover).
The key detail: when building max_reach, you only care about the left endpoint of each interval. Multiple intervals starting at the same position? Keep the one with the farthest right endpoint. That is exactly what max_reach[left] = max(max_reach[left], right) does.
2. Greedy farthest-reach jumping
This is the Jump Game II pattern. You maintain two variables: end (the boundary of your current jump) and farthest (the best you can do from anything in the current window). When you reach end, commit a jump and extend to farthest.
taps = 0
end = 0
farthest = 0
for i in range(n):
farthest = max(farthest, max_reach[i])
if i == end:
taps += 1
end = farthest
This skeleton solves any minimum-interval-covering problem once you have the max_reach array. You will see it in Video Stitching, Jump Game II, and now this taps problem. Learning it once means solving all three.
Edge cases
Single tap covers everything. If ranges[i] is large enough that [i - ranges[i], i + ranges[i]] contains [0, n], the answer is 1. The greedy algorithm handles this naturally because maxReach[0] will be at least n.
Impossible to cover. If there is a gap that no tap reaches, farthest will be stuck at or behind position i, and the algorithm returns -1. This happens when farthest is less than or equal to i during the scan.
Overlapping taps. Multiple taps may cover the same region. The max_reach array collapses overlapping coverage at the same start position, keeping only the best. The greedy scan then picks the minimum set.
Zero-range taps. A tap with ranges[i] = 0 covers only the single point i. It contributes nothing to the max_reach array (it sets max_reach[i] = max(max_reach[i], i), which does not extend reach). The algorithm effectively ignores it.
n = 0. The garden is a single point. It is trivially watered with zero taps. The loop range(0) runs zero iterations and returns taps = 0.
From understanding to recall
The solution is compact: one loop to build max_reach, one loop to greedily jump. But reproducing it under pressure requires remembering the details. Which index do you clamp to? Is it max_reach[left] or max_reach[right]? Do you check farthest before or after updating end?
These details stick when you practice writing the code from memory at spaced intervals. The pattern here is the same as Jump Game II, so once you have that building block locked in, this problem becomes a thin wrapper around it: just add the interval-to-maxReach conversion step.
Spaced repetition turns the two-step structure (convert intervals, then jump) into muscle memory. You see "minimum taps" or "minimum clips" or "minimum jumps" and the same greedy template flows out without hesitation.
Related posts
- Jump Game II - The problem this reduces to
- Minimum Number of Arrows to Burst Balloons - Interval greedy
- Video Stitching - Same interval covering pattern
CodeBricks breaks this problem into its interval-conversion and greedy-jump building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the reduction is automatic. When a new interval covering problem shows up in your interview, you do not hesitate. You just write it.