Minimum Number of Taps to Open to Water a Garden

Hard
865.

Minimum Number of Taps to Open to Water a Garden

Minimum Number of Taps to Open to Water a Garden is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Flipkart interviews.

A garden stretches along the x-axis from 0 to n. Tap i sits at position i and, when opened, waters the closed interval [i - ranges[i], i + ranges[i]].

Return the minimum number of taps to open so that the whole garden is watered, or -1 if it is impossible.

Example 1

Input
n = 5, ranges = [3,4,1,1,0,0]
Output
1
Explanation
Tap 1 alone waters [-3, 5], which covers the garden.

Example 2

Input
n = 3, ranges = [0,0,0,0]
Output
-1
Explanation
Every tap waters only its own point, leaving the gaps dry.

Example 3

Input
n = 7, ranges = [1,2,1,0,2,1,0,1]
Output
3

Constraints

  • 1 <= n <= 10000
  • ranges.length == n + 1
  • 0 <= ranges[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} ranges
 * @return {number}
 */
var minTaps = function(n, ranges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Taps to Open to Water a Garden — Solution

Minimum Number of Taps to Open to Water a Garden solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Taps to Open to Water a Garden is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Flipkart interviews.

Problem statement

A garden stretches along the x-axis from 0 to n. Tap i sits at position i and, when opened, waters the closed interval [i - ranges[i], i + ranges[i]].

Return the minimum number of taps to open so that the whole garden is watered, or -1 if it is impossible.

Example 1

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: Tap 1 alone waters [-3, 5], which covers the garden.

Example 2

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Every tap waters only its own point, leaving the gaps dry.

Example 3

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

Constraints

  • 1 <= n <= 10000
  • ranges.length == n + 1
  • 0 <= ranges[i] <= 100

Hints for Minimum Number of Taps to Open to Water a Garden

  1. Hint 1

    Turn each tap into the interval it waters, clamped to [0, n].

  2. Hint 2

    For each left endpoint, only the interval reaching furthest right matters.

  3. Hint 3

    Then it is the standard interval-covering greedy: jump to the furthest reachable point each time.

How to solve Minimum Number of Taps to Open to Water a Garden

Convert the taps into intervals, keep only the furthest reach per starting point, then cover [0, n] greedily — from everything already watered, jump to the furthest point any of those taps reaches.

Approach

  1. Build maxReach[l], the largest right endpoint among taps whose clamped interval starts at l.
  2. Sweep i from 0 to n - 1, tracking nxt, the furthest reach from any start seen so far.
  3. At each boundary curEnd, open a tap: if nxt <= i there is a dry gap and the answer is -1; otherwise count the tap and move the boundary to nxt.

Why it works

Only the furthest-reaching tap per start can be optimal — any other with the same start is contained in it. Committing at each boundary to the furthest reach is the classic covering greedy: delaying cannot reach further, and choosing a shorter interval forces at least as many taps later.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The intervals must be clamped to [0, n] before indexing, or a tap with a large range reads out of bounds.
  • A tap with range 0 waters a single point and can never bridge a gap.
  • The failure test is nxt <= i at a boundary — equality means no progress.

Reference solution

Python

from typing import List

def minTaps(n: int, ranges: List[int]) -> int:
    max_reach = [0] * (n + 1)
    for i, r in enumerate(ranges):
        l = max(0, i - r)
        right = min(n, i + r)
        max_reach[l] = max(max_reach[l], right)
    taps = cur_end = nxt = 0
    for i in range(n):
        nxt = max(nxt, max_reach[i])
        if i == cur_end:
            if nxt <= i:
                return -1
            taps += 1
            cur_end = nxt
    return taps

Java

public static 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, curEnd = 0, nxt = 0;
    for (int i = 0; i < n; i++) {
        nxt = Math.max(nxt, maxReach[i]);
        if (i == curEnd) {
            if (nxt <= i) return -1;
            taps++;
            curEnd = nxt;
        }
    }
    return taps;
}

C++

int minTaps(int n, vector<int>& ranges) {
    vector<int> maxReach(n + 1, 0);
    for (int i = 0; i <= n; i++) {
        int l = max(0, i - ranges[i]);
        int r = min(n, i + ranges[i]);
        maxReach[l] = max(maxReach[l], r);
    }
    int taps = 0, curEnd = 0, nxt = 0;
    for (int i = 0; i < n; i++) {
        nxt = max(nxt, maxReach[i]);
        if (i == curEnd) {
            if (nxt <= i) return -1;
            taps++;
            curEnd = nxt;
        }
    }
    return taps;
}

JavaScript

var minTaps = function(n, ranges) {
    var maxReach = [];
    for (var t = 0; t <= n; t++) maxReach.push(0);
    for (var i = 0; i <= n; i++) {
        var l = Math.max(0, i - ranges[i]);
        var r = Math.min(n, i + ranges[i]);
        if (r > maxReach[l]) maxReach[l] = r;
    }
    var taps = 0, curEnd = 0, nxt = 0;
    for (var j = 0; j < n; j++) {
        if (maxReach[j] > nxt) nxt = maxReach[j];
        if (j === curEnd) {
            if (nxt <= j) return -1;
            taps++;
            curEnd = nxt;
        }
    }
    return taps;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming