Minimum Number of Taps to Open to Water a Garden
HardPrompt
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] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach employs a straightforward greedy strategy. At each step, we aim to extend the watered portion of the garden as far as possible. We begin with the assumption that point 0 is our starting line. We then select a tap that can water point 0 (or any point already watered) and extends the furthest to the right. This process is repeated, with each new tap selection pushing the boundary of the watered area, until the entire garden from [0, n] is covered.
Algorithm
- Initialize
taps = 0andcurrent_end = 0.current_endrepresents the farthest point of the garden that is currently watered. - Start a loop that continues as long as the entire garden is not watered (
current_end < n). - Inside the loop, we decide to use one more tap, so increment
taps. - Find the best possible next tap. Initialize a variable
max_reach = current_end. - Iterate through all available taps from
i = 0ton. For each tap, calculate its watering interval[start, end]. - If a tap's interval starts at or before the currently watered point (
start <= current_end), it can be used to extend the coverage. Updatemax_reach = max(max_reach, end). - After checking all taps, if
max_reachhas not increased (i.e.,max_reach == current_end), it's impossible to extend the coverage further. This means the garden cannot be fully watered, so return -1. - Otherwise, update
current_end = max_reachto reflect the new watered area. - If the loop finishes, it means
current_end >= n, and the entire garden is watered. Return the totaltapsused.
Walkthrough
We maintain a variable, current_end, which tracks the rightmost boundary of the watered garden, initially set to 0. We also count the number of taps used. The main logic resides in a loop that runs as long as current_end is less than n. In each iteration of this loop, we simulate opening one more tap. To make the best choice, we scan through all n + 1 taps. For each tap, we determine its watering range [start, end]. If a tap can begin its watering at or before our current_end (start <= current_end), it's a candidate for our next choice. We find the candidate tap that offers the maximum possible new end point. This maximum end becomes our new current_end. If, after checking all taps, we find that we cannot extend our current_end at all, it signifies that we're stuck and can't water the rest of the garden, so we return -1. Otherwise, we continue this process until current_end reaches or surpasses n.
class Solution { public int minTaps(int n, int[] ranges) { int taps = 0; int current_end = 0; while (current_end < n) { taps++; int max_reach = current_end; for (int i = 0; i < ranges.length; i++) { int start = Math.max(0, i - ranges[i]); int end = Math.min(n, i + ranges[i]); if (start <= current_end) { max_reach = Math.max(max_reach, end); } } if (max_reach == current_end) { return -1; // Cannot extend coverage } current_end = max_reach; } return taps; }}Complexity
Time
O(T * n), where `T` is the final number of taps and `n` is the length of the garden. In the worst-case scenario, `T` can be proportional to `n`, leading to a time complexity of O(n^2).
Space
O(1) extra space, as we are only using a few variables to keep track of the state.
Trade-offs
Pros
The logic is intuitive and relatively easy to understand.
Cons
The time complexity of O(n^2) can be too slow and may result in a 'Time Limit Exceeded' error for large values of
n.
This approach refines the naive greedy strategy by pre-processing the tap ranges. Instead of repeatedly scanning all taps, we first convert them into intervals and sort these intervals by their starting points. This allows for a more efficient single pass to find the optimal next tap at each step. The core greedy choice remains the same: from the currently watered area, pick a tap that reaches the farthest.
Algorithm
- First, transform the
rangesarray into a list of intervals. For each tapi, create an interval[start, end]wherestart = max(0, i - ranges[i])andend = min(n, i + ranges[i]). - Sort this list of intervals based on their
startpoints in ascending order. - Initialize
taps = 0,current_end = 0,next_end = 0, and an interval pointeri = 0. - Begin a loop that continues as long as
current_end < n. - In each iteration, representing the selection of one tap, increment
taps. - Use a nested loop to iterate through the sorted intervals (starting from index
i) as long as their start point is within the currently watered range (intervals[i].start <= current_end). For each such interval, updatenext_endto be the maximum end point seen so far (next_end = max(next_end, intervals[i].end)). - After the inner loop, if
next_endhas not advanced beyondcurrent_end, it's impossible to proceed. Return -1. - Update
current_end = next_end. - If the main loop completes, return
taps.
Walkthrough
The first step is to represent each tap as an interval [start, end]. We create a list of these intervals. Then, we sort this list based on the start values. This sorting is key, as it allows us to consider taps in the order of their starting positions.
We then proceed with the greedy selection. We use current_end to track our progress. In each step, we need to select a new tap. We look at all the intervals that can be 'activated' from our current position (i.e., their start is less than or equal to current_end). Thanks to the sorting, these intervals will be contiguous in our list. We iterate through them, find the one that provides the maximum end, and set that as our next_end. We then update current_end to this next_end and increment our tap count. A single pointer i is used to traverse the sorted interval list, ensuring we don't re-evaluate intervals unnecessarily.
import java.util.Arrays;import java.util.Comparator; class Solution { public int minTaps(int n, int[] ranges) { int[][] intervals = new int[n + 1][2]; for (int i = 0; i <= n; i++) { intervals[i][0] = Math.max(0, i - ranges[i]); intervals[i][1] = Math.min(n, i + ranges[i]); } Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); int taps = 0; int current_end = 0; int next_end = 0; int i = 0; while (current_end < n) { taps++; while (i <= n && intervals[i][0] <= current_end) { next_end = Math.max(next_end, intervals[i][1]); i++; } if (next_end <= current_end) { return -1; // Cannot make progress } current_end = next_end; } return taps; }}Complexity
Time
O(n log n), dominated by the sorting of intervals. The subsequent greedy selection loop runs in O(n) time because we iterate through the intervals with a single pass.
Space
O(n) to store the list of intervals.
Trade-offs
Pros
Significantly more efficient than the naive O(n^2) approach.
It's a standard and robust pattern for solving interval-based covering problems.
Cons
The sorting step has a time complexity of O(n log n), which is the bottleneck for this approach.
This approach is the most optimal, achieving a linear time solution. It cleverly avoids the O(n log n) sorting step by using an auxiliary array. The problem is reframed into a variant of the 'Jump Game II' problem. We first precompute the maximum reach from every possible starting point in the garden. Then, we use a greedy algorithm to make the minimum number of 'jumps' (i.e., open the minimum number of taps) to cover the garden from 0 to n.
Algorithm
- Create an auxiliary array
max_reachof sizen + 1, initialized to all zeros. - Iterate through the taps from
i = 0ton. For each tap, calculate its range[start, end]. - For each tap, update
max_reach[start] = max(max_reach[start], end). After this loop,max_reach[i]will store the farthest point reachable from any tap whose range starts ati. - Now, solve the problem using a greedy approach similar to the 'Jump Game II' problem.
- Initialize
taps = 0,current_end = 0(farthest reach withtapstaps), andnext_end = 0(farthest reach withtaps + 1taps). - Iterate through the garden from
i = 0ton - 1. - In each iteration, update the potential next reach:
next_end = max(next_end, max_reach[i]). - If the current position
iis the boundary of our current reach (i == current_end), it means we must use a tap. We incrementtapsand updatecurrent_endtonext_end. - If
current_endever becomes greater than or equal ton, we have successfully covered the garden, and we can stop and return the tap count. - If the loop finishes and
current_end < n, it's impossible to cover the garden, so return -1.
Walkthrough
The key insight is to efficiently find the maximum reach from any given point. We create an array max_reach of size n + 1. We process the ranges array once: for each tap i, it defines an interval [start, end]. We use this to update our max_reach array such that max_reach[start] stores the maximum possible end for any tap starting at start. This precomputation takes O(n) time.
With the max_reach array, the problem becomes: starting at index 0, at each position i, you can 'jump' to any position up to max_reach[i]. What is the minimum number of jumps to reach or exceed n? This can be solved greedily in a single pass. We keep track of current_end (the farthest we can get with the current taps) and next_end (the farthest we can get with one more tap). As we iterate through the garden points i, we update next_end. When i reaches current_end, it's time to 'jump' – we increment our tap count and set current_end to the new next_end we found.
class Solution { public int minTaps(int n, int[] ranges) { int[] max_reach = new int[n + 1]; for (int i = 0; i <= n; i++) { int start = Math.max(0, i - ranges[i]); int end = Math.min(n, i + ranges[i]); max_reach[start] = Math.max(max_reach[start], end); } int taps = 0; int current_end = 0; int next_end = 0; for (int i = 0; i < n; i++) { if (i > next_end) { // Current position is unreachable return -1; } next_end = Math.max(next_end, max_reach[i]); if (i == current_end) { // Must use a new tap taps++; current_end = next_end; } } // If current_end can't reach n, it's impossible return current_end >= n ? taps : -1; }}Complexity
Time
O(n). The precomputation step to build the `max_reach` array is O(n), and the final greedy pass is also O(n).
Space
O(n) for the auxiliary `max_reach` array.
Trade-offs
Pros
Achieves the best possible time complexity of O(n).
Highly efficient for large inputs.
Cons
The logic can be slightly less intuitive as it transforms the problem into another known pattern ('Jump Game').
Solutions
Solution
class Solution {public int minTaps(int n, int[] ranges) { int[] last = new int[n + 1]; for (int i = 0; i < n + 1; ++i) { int l = Math.max(0, i - ranges[i]), r = i + ranges[i]; last[l] = Math.max(last[l], r); } int ans = 0, mx = 0, pre = 0; for (int i = 0; i < n; ++i) { mx = Math.max(mx, last[i]); if (mx <= i) { return -1; } if (pre == i) { ++ans; pre = mx; } } return ans; }}class Solution {public: int minTaps(int n, vector<int> &ranges) { vector<int> last(n + 1); for (int i = 0; i < n + 1; ++i) { int l = max(0, i - ranges[i]), r = i + ranges[i]; last[l] = max(last[l], r); } int ans = 0, mx = 0, pre = 0; for (int i = 0; i < n; ++i) { mx = max(mx, last[i]); if (mx <= i) { return -1; } if (pre == i) { ++ans; pre = mx; } } return ans; }};class Solution: def minTaps(self, n: int, ranges: List[int]) -> int: last = [0] * (n + 1) for i, x in enumerate(ranges): l, r = max(0, i - x), i + x last[l] = max(last[l], r) ans = mx = pre = 0 for i in range(n): mx = max(mx, last[i]) if mx <= i: return - 1 if pre == i: ans += 1 pre = mx return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.