Given n+1 taps at positions 0..n, each covering a range, find minimum taps to cover garden [0,n].
Input: n=5, ranges=[3,4,1,1,0,0] → Output: 1. Tap 1 covers 0..5.
Input: n=3, ranges=[0,0,0,0] → Output: -1
Convert to jump game: for each position, find farthest right reach. Then find min jumps.
- Create maxReach[n+1] array
- For each tap i: left=max(0,i-ranges[i]), right=min(n,i+ranges[i])
- Update maxReach[left] = max(maxReach[left], right)
- Apply jump game II: count jumps from 0 to n
- Return count or -1 if unreachable
public int minTaps(int n, int[] ranges) {
int[] maxReach = new int[n + 1];
for (int i = 0; i <= n; i++) {
int l = Math.max(0, i - ranges[i]);
maxReach[l] = Math.max(maxReach[l], i + ranges[i]);
}
int taps = 0, curEnd = 0, farthest = 0;
for (int i = 0; i <= n; i++) {
if (i > farthest) return -1;
farthest = Math.max(farthest, maxReach[i]);
if (i == curEnd && i < n) {
taps++;
curEnd = farthest;
}
}
return taps;
}
- Time Complexity: O(n)
- Space Complexity: O(n)