Minimum Number of Taps to Water Garden

Master this topic with zero to advance depth.

Minimum Number of Taps to Water Garden

There is a one-dimensional garden from 0 to n. There are n + 1 taps at points [0, 1, ..., n]. Tap i can water the area [i - ranges[i], i + ranges[i]].

Return the minimum number of taps to water the entire garden [0, n]. If impossible, return -1.

Visual Representation

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

Tap 0: [0, 3]
Tap 1: [0, 5] <--- Covers everything alone!
Tap 2: [1, 3]
...

Optimal: 1 (Tap 1)

Hard

Examples

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Tap at index 1 covers [0,5], which is the entire garden.

Approach 1

Level I: Brute Force (Recursive Backtracking)

Intuition

Try every subset of taps and check if they together cover the garden [0, n]. This can be implemented using recursion by deciding for each tap whether to include it or not.

Thought Process

solve(tapIdx, currentCoverage)
At each step, either take the current tap or skip it.
Base case: If tapIdx == n + 1, check if currentCoverage >= n.
This approach is extremely slow due to $2^N$ combinations.

⏱ O(2^N)💾 O(N)

Detailed Dry Run

n=3, taps=[[0,2], [1,3]]

solve(0, 0): Take [0,2] -> solve(1, 2) -> Take [1,3] -> solve(2, 3) -> SUCCESS (2 taps)
solve(0, 0): Skip [0,2] -> solve(1, 0) -> Take [1,3] -> FAIL (Gap at [0,1])

java

public class Solution {
    int min = 10001;
    public int minTaps(int n, int[] ranges) {
        solve(0, n, ranges, 0, 0);
        return min > 1000 ? -1 : min;
    }
    void solve(int idx, int n, int[] rs, int count, int reach) {
        if (reach >= n) { min = Math.min(min, count); return; }
        if (idx > n) return;
        int l = Math.max(0, idx - rs[idx]), r = Math.min(n, idx + rs[idx]);
        if (l <= reach) solve(idx+1, n, rs, count+1, Math.max(reach, r));
        solve(idx+1, n, rs, count, reach);
    }
}

Approach 2

Level II: Dynamic Programming

Intuition

Define dp[i] as the minimum number of taps needed to water the garden from index $0$ to $i$ . For each tap, we update all indices it covers.

Thought Process

Initialize dp array of size n+1 with a large value (infinity).
dp[0] = 0 (no taps needed to cover index 0).
For each tap i with range [left, right]:
- For every j such that left <= j <= right:
  - dp[right] = min(dp[right], dp[j] + 1).

Pattern: Interval DP / Shortest Path in DAG

⏱ O(N * MaxRange)💾 O(N)

Detailed Dry Run

n=5, ranges=[3,4,1,1,0,0], dp=[0, inf, inf, inf, inf, inf]

Tap 0: [0,3]. dp[1..3] = min(inf, dp[0]+1) = 1. dp=[0, 1, 1, 1, inf, inf]
Tap 1: [0,5]. dp[1..5] = min(cur, dp[0..1]+1) = 1. dp=[0, 1, 1, 1, 1, 1]

java

public class Solution {
    public int minTaps(int n, int[] ranges) {
        int[] dp = new int[n + 1];
        java.util.Arrays.fill(dp, n + 2);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            int l = Math.max(0, i - ranges[i]);
            int r = Math.min(n, i + ranges[i]);
            for (int j = l; j <= r; j++) {
                dp[r] = Math.min(dp[r], dp[j] + 1);
            }
        }
        return dp[n] > n ? -1 : dp[n];
    }
}

Approach 3

Level III: Optimal Greedy (Jump Game II Variation)

Intuition

This is equivalent to finding the minimum jumps to reach n. We transform each tap into a 'jump' from its left boundary to its right boundary.

Thought Process

Preprocess: For each start point $i$ , find the maximum end point it can reach: maxReach[left] = max(maxReach[left], right).
Now it's Jump Game II: Iterate from $0$ to $n-1$ , keeping track of the current coverage end and the farthest reach possible.

Pattern: Interval Coverage / Jump Game II

⏱ O(N) - One pass for preprocessing, one for greedy.💾 O(N) for maxReach array.

Detailed Dry Run

n=5, ranges=[3,4,1,1,0,0] MaxReach: [5, 0, 3, 0, 4, 5] (Index 0 can reach 5 via Tap 1)

i	farthest	end	taps	Action
0	5	0	1	i == end, taps++, end = 5
1-4	5	5	1	farthest doesn't change
Result: 1

java

public class Solution {
    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]);
            int r = Math.min(n, i + ranges[i]);
            maxReach[l] = Math.max(maxReach[l], r);
        }
        int taps = 0, currEnd = 0, farthest = 0;
        for (int i = 0; i < n; i++) {
            farthest = Math.max(farthest, maxReach[i]);
            if (farthest <= i) return -1; // Gap
            if (i == currEnd) {
                taps++;
                currEnd = farthest;
            }
        }
        return taps;
    }
}

← Previous QuestionTask Scheduler

Next Question →Maximum Length of Pair Chain

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.