Minimum Number of Taps to Open to Water a Garden

Minimum Number of Taps to Open to Water a Garden - Problem

There is a one-dimensional garden on the x-axis. The garden starts at point 0 and ends at point n (i.e., the length of the garden is n).

There are n + 1 taps located at points [0, 1, 2, ..., 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, ranges = [3,4,1,1,0,0]

› Output: 1

💡 Note: Tap at index 1 has range 4, so it can water area [1-4, 1+4] = [-3,5]. Since we only need [0,5], tap 1 alone covers the entire garden.

Example 2 — Multiple Taps Needed

$ Input: n = 3, ranges = [0,0,0,0]

› Output: -1

💡 Note: No tap has any range (all ranges are 0), so no tap can water any area beyond its own position. Cannot water the entire garden.

Example 3 — Optimal Selection

$ Input: n = 7, ranges = [1,2,1,0,2,1,0,1]

› Output: 3

💡 Note: We can use taps at positions 1, 4, and 7. Tap 1 covers [0,3], tap 4 covers [2,6], tap 7 covers [6,8]. Together they cover [0,7].

Constraints

1 ≤ n ≤ 10⁴
ranges.length == n + 1
0 ≤ ranges[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Garden of length n=5, taps at positions 0-5 with given ranges

Coverage

Each tap covers interval [position - range, position + range]

Output

Minimum number of taps needed to cover entire garden [0,n]

Key Takeaway

🎯 Key Insight: Use greedy approach - at each step pick the tap that extends coverage furthest, similar to Jump Game II

Asked in

G Google 23 a Amazon 18 M Microsoft 12 A Apple 8

The key insight is to use a greedy approach similar to Jump Game II. We track the furthest position reachable from each point and greedily select taps that extend our coverage the most. Best approach is Greedy with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n × sum(ranges))	O(n)	Use DP to track minimum taps needed to water up to each position
Brute Force - Try All Combinations	O(2^n × n)	O(n)	Try every possible subset of taps to find minimum that covers entire garden
Greedy Approach	O(n²)	O(n)	Always pick the tap that extends coverage the furthest from current position

Dynamic Programming — Algorithm Steps

Initialize dp array with infinity except dp[0] = 0
For each tap, update all positions it can cover
Return dp[n] if garden can be watered

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

dp[0] = 0, all others = infinity

Process Taps

For each tap, update positions it can reach

Get Result

dp[n] contains minimum taps needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n, int* ranges, int rangesSize) {
    // dp[i] = minimum taps needed to water garden from 0 to i
    int* dp = malloc((n + 1) * sizeof(int));
    for (int i = 0; i <= n; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    for (int i = 0; i < rangesSize; i++) {
        int left = max(0, i - ranges[i]);
        int right = min(n, i + ranges[i]);
        
        // If this tap can cover position left, update all positions it can reach
        if (dp[left] != INT_MAX) {
            for (int j = left; j <= right; j++) {
                if (dp[left] + 1 < dp[j]) {
                    dp[j] = dp[left] + 1;
                }
            }
        }
    }
    
    int result = dp[n] == INT_MAX ? -1 : dp[n];
    free(dp);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    int* ranges = malloc((n + 1) * sizeof(int));
    char* token = strtok(line + 1, ",]");
    int i = 0;
    while (token != NULL && i <= n) {
        ranges[i] = atoi(token);
        token = strtok(NULL, ",]");
        i++;
    }
    
    int result = solution(n, ranges, n + 1);
    printf("%d\n", result);
    
    free(ranges);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × sum(ranges))

For each tap, we update all positions in its range

✓ Linear Growth

Space Complexity

O(n)

DP array of size n+1 to store minimum taps for each position

⚡ Linearithmic Space

52.0K Views

Medium Frequency

~25 min Avg. Time

1.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler