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

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

✓ Brute Force - Try All Combinations

⏱️ Time: O(2^n × n) Space: O(n)

Generate all possible combinations of taps and check which ones completely cover the garden [0, n]. Return the minimum size combination that works.

Dynamic Programming

⏱️ Time: O(n × sum(ranges)) Space: O(n)

Create a DP array where dp[i] represents the minimum number of taps needed to water the garden from position 0 to position i.

Greedy Approach

⏱️ Time: O(n²) Space: O(n)

Use a greedy strategy similar to Jump Game II. At each position, find the tap that can reach that position and extends the furthest to the right.

Brute Force - Try All Combinations — Algorithm Steps

Generate all 2^(n+1) possible subsets of taps
For each subset, check if it covers the entire garden [0, n]
Return the smallest valid subset size

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^(n+1) possible combinations of taps

Check Coverage

For each subset, verify it covers entire garden [0,n]

Find Minimum

Return smallest valid subset size

Code -

solution.c — C

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

typedef struct {
    int left;
    int right;
} Interval;

int compareIntervals(const void* a, const void* b) {
    Interval* ia = (Interval*)a;
    Interval* ib = (Interval*)b;
    if (ia->left != ib->left) {
        return ia->left - ib->left;
    }
    return ia->right - ib->right;
}

int solution(int n, int* ranges, int rangesSize) {
    // Convert taps to intervals
    Interval* intervals = malloc(rangesSize * sizeof(Interval));
    int intervalCount = 0;
    
    for (int i = 0; i < rangesSize; i++) {
        int left = (i - ranges[i] > 0) ? i - ranges[i] : 0;
        int right = (i + ranges[i] < n) ? i + ranges[i] : n;
        if (left <= right) {  // Valid interval
            intervals[intervalCount].left = left;
            intervals[intervalCount].right = right;
            intervalCount++;
        }
    }
    
    if (intervalCount == 0) {
        free(intervals);
        return -1;
    }
    
    // Sort intervals by start position
    qsort(intervals, intervalCount, sizeof(Interval), compareIntervals);
    
    // Greedy approach to cover [0, n]
    int taps = 0;
    int current_end = 0;
    int i = 0;
    
    while (current_end < n) {
        if (i >= intervalCount || intervals[i].left > current_end) {
            free(intervals);
            return -1;  // Gap that cannot be covered
        }
        
        // Find the interval that starts at or before current_end
        // and extends the farthest
        int max_end = current_end;
        while (i < intervalCount && intervals[i].left <= current_end) {
            if (intervals[i].right > max_end) {
                max_end = intervals[i].right;
            }
            i++;
        }
        
        if (max_end == current_end) {
            free(intervals);
            return -1;  // No progress made
        }
        
        current_end = max_end;
        taps++;
    }
    
    free(intervals);
    return taps;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    int* ranges = malloc((n + 1) * sizeof(int));
    int count = 0;
    
    // Parse the array manually
    char* p = line;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']' && count <= n) {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        
        char* endptr;
        ranges[count] = (int)strtol(p, &endptr, 10);
        p = endptr;
        count++;
    }
    
    int result = solution(n, ranges, n + 1);
    printf("%d\n", result);
    
    free(ranges);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

2^n subsets to try, each taking O(n) time to validate coverage

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack and temporary arrays for subset validation

⚡ 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler