There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e., the length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
Example 1:
Input: n = 5, ranges = [3,4,1,1,0,0] Output: 1 Explanation: The tap at point 0 can cover the interval [-3,3] The tap at point 1 can cover the interval [-3,5] The tap at point 2 can cover the interval [1,3] The tap at point 3 can cover the interval [2,4] The tap at point 4 can cover the interval [4,4] The tap at point 5 can cover the interval [5,5] Opening Only the second tap will water the whole garden [0,5]
Example 2:
Input: n = 3, ranges = [0,0,0,0] Output: -1 Explanation: Even if you activate all the four taps you cannot water the whole garden.
Constraints:
1 <= n <= 104ranges.length == n + 10 <= ranges[i] <= 100Problem Overview: You have a one-dimensional garden from 0 to n. Each tap at position i waters an interval [i - ranges[i], i + ranges[i]]. The task is to open the minimum number of taps so the entire garden is covered. If full coverage is impossible, return -1.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
Dynamic programming treats the garden like a reachability problem. Create a dp array where dp[i] stores the minimum taps needed to cover the segment [0, i]. For each tap, compute the interval it covers and try updating all reachable positions inside that interval. This means iterating through previous states and relaxing transitions similar to interval DP. The approach is straightforward and helps reason about partial coverage, but the nested updates lead to O(n²) time in the worst case. Useful when building intuition about interval coverage or when greedy reasoning is not immediately obvious.
Approach 2: Greedy Interval Covering (O(n) time, O(n) space)
The optimal solution converts the problem into a classic interval covering task, similar to the Jump Game greedy strategy. First preprocess taps to compute the farthest right boundary reachable from every left boundary. Then iterate from left to right while tracking the current coverage and the farthest extension possible from taps encountered so far. When the iteration reaches the end of the current coverage, you must "open" a new tap by extending to the farthest reachable boundary. This greedy expansion guarantees the minimum number of taps because each step maximizes coverage. The algorithm runs in O(n) time and uses O(n) extra space for preprocessing.
The key insight: always extend the coverage as far as possible before committing to opening another tap. This prevents unnecessary tap activations and mirrors optimal interval scheduling strategies used in many greedy problems.
The preprocessing step relies on scanning the array of ranges and computing coverage boundaries, while the greedy sweep handles the minimal selection logic. An alternative formulation using dynamic programming exists, but it is slower.
Recommended for interviews: The greedy interval covering solution. Interviewers expect candidates to recognize the connection to Jump Game–style greedy expansion. Mentioning the DP formulation first shows you understand the state transition, but implementing the O(n) greedy strategy demonstrates strong algorithmic insight.
This approach involves treating each tap as an interval [i-ranges[i], i+ranges[i]], and seeking the minimal number of such intervals required to cover the entire garden range [0, n]. The key is to employ a greedy algorithm which iteratively selects the interval that extends the coverage furthest at each point. Specifically, from each starting point, choose the interval that reaches farthest within the current range, then jump to the furthest point reached by the selected intervals and repeat the process.
This C solution first transforms the ranges into maximum right reach for each start position. It employs a greedy approach, moving through the garden while extending the reach of water as far as possible with the least number of taps activated. If a gap or unwatered region is found, it returns -1.
Time Complexity: O(n), as the algorithm processes the tap ranges in a single pass.
Space Complexity: O(n), due to the storage for the maxRange array.
This approach takes on the problem by formulating it into a dynamic programming challenge. Here, the idea is to maintain an array dp[], where dp[i] denotes the minimum number of taps required to water up to position i. Start by initializing dp[i] with infinity, except dp[0]=0, then update each dp[i] by considering if current tap can extend water coverage from any previous dp positions.
This C implementation establishes an array, dp[], with each index representing the minimal taps needed to reach that point. By updating the array through possible coverage ranges of each tap, it identifies the least number capable to span the whole garden.
Time Complexity: O(n^2), due to the potential iteration across all tap ranges for each garden position.
Space Complexity: O(n), as a dp array of size n+1 is maintained.
We note that for all taps that can cover a certain left endpoint, choosing the tap that can cover the farthest right endpoint is optimal.
Therefore, we can preprocess the array ranges. For the i-th tap, it can cover the left endpoint l = max(0, i - ranges[i]) and the right endpoint r = i + ranges[i]. We calculate the position of the tap that can cover the left endpoint l with the farthest right endpoint and record it in the array last[i].
Then we define the following three variables:
ans represents the final answer, i.e., the minimum number of taps;mx represents the farthest right endpoint that can currently be covered;pre represents the farthest right endpoint covered by the previous tap.We traverse all positions in the range [0, ldots, n-1]. For the current position i, we use last[i] to update mx, i.e., mx = max(mx, last[i]).
mx leq i, it means the next position cannot be covered, so we return -1.pre = i, it means a new subinterval needs to be used, so we increment ans by 1 and update pre = mx.After the traversal, we return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the garden.
Similar problems:
| Approach | Complexity |
|---|---|
| Greedy Interval Covering | Time Complexity: O(n), as the algorithm processes the tap ranges in a single pass. |
| Dynamic Programming | Time Complexity: O(n^2), due to the potential iteration across all tap ranges for each garden position. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n) | When exploring state transitions or building intuition about interval coverage |
| Greedy Interval Covering | O(n) | O(n) | Optimal solution for large inputs and typical interview expectations |
Minimum Number of Taps to Open to Water a Garden | Full Dry Run | ATLASSIAN | Leetcode - 1326 • codestorywithMIK • 15,536 views views
Watch 9 more video solutions →Practice Minimum Number of Taps to Open to Water a Garden with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor