Watch 10 video solutions for Minimum Number of Taps to Open to Water a Garden, a hard level problem involving Array, Dynamic Programming, Greedy. This walkthrough by codestorywithMIK has 15,536 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |