Minimum Number of Taps to Open to Water a Garden

hard greedy intervals

Problem

A garden lies on the x-axis from 0 to n. Tap i is at position i and waters [i - ranges[i], i + ranges[i]]. Return the minimum number of taps that must be open to water the entire garden, or -1 if impossible.

Inputn = 5, ranges = [3,4,1,1,0,0]

Output1

Tap 1 alone covers [-3, 5] which includes [0, 5].

ranges (comma-separated)

def min_taps(n, ranges):
    reach = [0] * (n + 1)
    for i, r in enumerate(ranges):
        l = max(0, i - r); rr = min(n, i + r)
        reach[l] = max(reach[l], rr)
    taps = 0; cur_end = 0; far = 0
    for i in range(n + 1):
        if i > far: return -1
        if i > cur_end:
            taps += 1; cur_end = far
        far = max(far, reach[i])
    return taps if cur_end >= n else -1

function minTaps(n, ranges) {
  const reach = new Array(n + 1).fill(0);
  for (let i = 0; i < ranges.length; i++) {
    const l = Math.max(0, i - ranges[i]);
    const r = Math.min(n, i + ranges[i]);
    reach[l] = Math.max(reach[l], r);
  }
  let taps = 0, curEnd = 0, far = 0;
  for (let i = 0; i <= n; i++) {
    if (i > far) return -1;
    if (i > curEnd) { taps++; curEnd = far; }
    far = Math.max(far, reach[i]);
  }
  return curEnd >= n ? taps : -1;
}

class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] reach = new int[n + 1];
        for (int i = 0; i < ranges.length; i++) {
            int l = Math.max(0, i - ranges[i]);
            int r = Math.min(n, i + ranges[i]);
            reach[l] = Math.max(reach[l], r);
        }
        int taps = 0, curEnd = 0, far = 0;
        for (int i = 0; i <= n; i++) {
            if (i > far) return -1;
            if (i > curEnd) { taps++; curEnd = far; }
            far = Math.max(far, reach[i]);
        }
        return curEnd >= n ? taps : -1;
    }
}

int minTaps(int n, vector<int>& ranges) {
    vector<int> reach(n + 1, 0);
    for (int i = 0; i < (int)ranges.size(); i++) {
        int l = max(0, i - ranges[i]);
        int r = min(n, i + ranges[i]);
        reach[l] = max(reach[l], r);
    }
    int taps = 0, curEnd = 0, far = 0;
    for (int i = 0; i <= n; i++) {
        if (i > far) return -1;
        if (i > curEnd) { taps++; curEnd = far; }
        far = max(far, reach[i]);
    }
    return curEnd >= n ? taps : -1;
}

Explanation

Each tap waters an interval, so this is really a jump game: cover the line from 0 to n using as few overlapping intervals as possible. We solve it with a greedy farthest-reach sweep.

First we turn taps into reach: for tap i we compute its interval [i-r, i+r] (clamped to [0, n]) and store reach[l] = max(reach[l], rr), the farthest right end among taps that start at position l.

Then we walk positions 0..n tracking far (best reach seen so far) and cur_end (end of the current tap's coverage). When we pass cur_end, we must open another tap, so taps += 1 and jump cur_end to far. If position i ever goes beyond far, there is a gap nothing covers and we return -1.

Example: n = 5, ranges = [3,4,1,1,0,0]. Tap 1 reaches from -3 to 5, covering all of [0,5] by itself, so the answer is 1.

Always extending to the farthest reachable point uses the fewest taps, the same logic as minimum jumps to the end of an array.

Time: O(n) Space: O(n)