Get started

Minimum Number of Taps to Open to Water a Garden — Hard Problem & Solution

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]].

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue