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] <= 100The garden is represented as a line segment [0, n], and each tap waters an interval based on its range. The core challenge is to select the minimum number of intervals that completely cover the garden. A useful transformation is to convert each tap into a watering interval [left, right] and then reason about coverage.
The most efficient method uses a greedy strategy similar to Jump Game II. First preprocess the intervals so that for each position you know the farthest point that can be reached. Then iterate across the garden while tracking the current coverage and the farthest next reach. Whenever you exhaust the current coverage, you "open" another tap to extend the range. If no extension is possible, watering the entire garden is impossible.
An alternative dynamic programming approach considers the minimum taps needed to reach each position, but it is less efficient. The greedy interval-expansion method achieves optimal performance with linear traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Interval Expansion | O(n) | O(n) |
| Dynamic Programming | O(n^2) | O(n) |
Happy Coding
Use these hints if you're stuck. Try solving on your own first.
Create intervals of the area covered by each tap, sort intervals by the left end.
We need to cover the interval [0, n]. we can start with the first interval and out of all intervals that intersect with it we choose the one that covers the farthest point to the right.
What if there is a gap between intervals that is not covered ? we should stop and return -1 as there is some interval that cannot be covered.
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.
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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int minTaps(int n, vector<int>& ranges) {
8 vector<int> maxRange(n + 1, 0);
9 for (int i = 0; i <= n; ++i) {
10 int left = max(0, i - ranges[i]);
11 int right = min(n, i + ranges[i]);
12 maxRange[left] = max(maxRange[left], right);
}
int taps = 0, currEnd = 0, nextEnd = 0;
for (int i = 0; i <= n; ++i) {
if (i > nextEnd) return -1;
if (i > currEnd) {
taps++;
currEnd = nextEnd;
}
nextEnd = max(nextEnd, maxRange[i]);
}
return taps;
}
};The C++ solution follows a similar strategy as the C implementation. It computes the maximum right extension for each leftmost point, then proceeds with a greedy logic to expand the watering coverage using minimum taps possible.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Both problems involve extending the farthest reachable position while traversing an array. In this tap problem, watering intervals behave like jumps that extend coverage, making the greedy strategy very similar to the Jump Game II solution.
Yes, this problem is representative of interval coverage and greedy optimization patterns often discussed in technical interviews. Variants of this problem can appear in companies like Google, Amazon, and Meta.
An array is typically used to store the farthest reach for each starting position after converting taps into intervals. This preprocessing step enables an efficient greedy traversal across the garden.
The optimal approach uses a greedy interval coverage strategy similar to Jump Game II. By preprocessing the farthest reachable point from each position, you can expand coverage while counting the minimum taps needed. This allows the garden to be covered in linear time.
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.