LeetCode 1326 - Minimum Number of Taps to Open to Water a Garden

LeetCode Problem 1326

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem describes a one-dimensional garden that stretches from position 0 to position n. At every integer position i, there is a tap that may water some interval around it. Specifically, if tap i is opened, it covers the interval:

$$[i - ranges[i],\ i + ranges[i]]$$

The goal is to determine the minimum number of taps needed so that every point in the garden from 0 through n is covered by at least one tap.

This is fundamentally an interval coverage problem. Every tap creates an interval on the number line, and we want to choose the smallest number of intervals that together completely cover [0, n].

The input consists of:

• An integer n, representing the garden length.
• An array ranges of size n + 1.
• Each ranges[i] indicates how far tap i can spray to the left and right.

The output should be:

• The minimum number of taps required to cover the entire garden.
• -1 if complete coverage is impossible.

The constraints are important:

• n <= 10^4
• ranges[i] <= 100

Since n is moderately large, exponential or quadratic brute-force solutions may become too slow. We need something close to linear time.

Several edge cases are especially important:

• All taps may have zero range, making coverage impossible.
• One tap may already cover the entire garden.
• There may be gaps between intervals.
• Multiple taps may overlap heavily.
• Some intervals may extend beyond 0 or n, which is acceptable and should simply be clamped logically.

The key challenge is minimizing the number of chosen intervals while guaranteeing continuous coverage.

Approaches

Brute Force Approach

A brute-force solution would try all combinations of taps and check whether the selected set covers the entire interval [0, n].

For every subset of taps:

1. Compute the intervals covered.
2. Merge overlapping intervals.
3. Check whether [0, n] is fully covered.
4. Track the minimum number of taps used.

This approach is correct because it exhaustively explores all possible choices. However, it is computationally infeasible.

There are 2^(n+1) possible subsets of taps. Even for relatively small values of n, this becomes astronomically large.

A slightly improved brute-force approach might use dynamic programming over intervals, but even that can still become quadratic or worse.

Key Insight

This problem is equivalent to the classic "minimum intervals to cover a line segment" problem, which can be solved greedily.

The important observation is:

For every starting position, we only care about the tap that extends coverage the farthest.

This transforms the problem into something very similar to the Jump Game II problem.

We preprocess the intervals so that:

• max_reach[left] stores the farthest right endpoint reachable from position left.

Then we greedily expand coverage:

• At every step, we choose the interval that extends the current reachable boundary as far as possible.
• When we exhaust the current coverage range, we must open another tap.

This greedy strategy works because choosing the farthest-reaching interval always preserves the optimal solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Tries every subset of taps
Optimal Greedy	O(n)	O(n)	Converts intervals into Jump Game style coverage

Algorithm Walkthrough

Step 1: Convert taps into intervals

Each tap i covers:

$$[i - ranges[i],\ i + ranges[i]]$$

We compute:

• left = max(0, i - ranges[i])
• right = min(n, i + ranges[i])

This gives the effective interval within the garden boundaries.

Step 2: Build the farthest reach array

We create an array:

max_reach[left]

For every interval [left, right], we store:

max_reach[left] = max(max_reach[left], right)

This means:

• Starting from position left,
• the farthest coverage we can obtain is right.

Step 3: Perform greedy interval expansion

We now iterate from 0 to n.

We maintain three variables:

• taps_used
• current_end
• farthest

Their meanings are:

• current_end is the boundary covered by the currently selected taps.
• farthest is the farthest boundary reachable while scanning positions inside the current interval.
• taps_used counts how many taps we opened.

Step 4: Expand the farthest reachable boundary

At each position i:

farthest = max(farthest, max_reach[i])

This simulates considering all intervals that begin at or before i.

Step 5: Detect impossible coverage

If:

i > farthest

then no interval can cover position i.

In that case, return -1.

Step 6: Open a new tap when necessary

Whenever we reach:

i == current_end

we have exhausted the coverage from previously chosen taps.

We must:

1. Open another tap.
2. Extend coverage to farthest.

So:

taps_used += 1
current_end = farthest

Step 7: Finish once coverage reaches n

As soon as current_end >= n, the entire garden is covered.

Return taps_used.

Why it works

The greedy strategy always chooses the interval that extends coverage the farthest among all currently available intervals.

At any point, delaying the choice cannot improve the solution because all intervals starting before the current boundary are already known. Choosing the farthest-reaching one maximizes future flexibility and minimizes the number of selections.

This is the same correctness argument used in Jump Game II and minimum interval coverage problems.

Python Solution

from typing import List

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        max_reach = [0] * (n + 1)

        # Convert taps into interval coverage
        for i in range(n + 1):
            left = max(0, i - ranges[i])
            right = min(n, i + ranges[i])

            max_reach[left] = max(max_reach[left], right)

        taps_used = 0
        current_end = 0
        farthest = 0

        for i in range(n + 1):
            if i > farthest:
                return -1

            farthest = max(farthest, max_reach[i])

            if i == current_end:
                if current_end != n:
                    taps_used += 1
                    current_end = farthest

                    if current_end >= n:
                        return taps_used

        return 0 if n == 0 else -1

The implementation begins by transforming each tap into an interval. Instead of storing every interval separately, we compress the information into max_reach, where each index represents the farthest point reachable from that left boundary.

The greedy traversal resembles breadth expansion in Jump Game II. While scanning positions inside the currently covered range, we continuously update farthest.

When we reach the edge of the current coverage interval, we are forced to activate another tap. At that moment, we extend coverage to the best possible farthest boundary discovered so far.

If at any point the current index exceeds farthest, it means there is a gap in coverage and the garden cannot be fully watered.

Go Solution

func minTaps(n int, ranges []int) int {
    maxReach := make([]int, n+1)

    // Convert taps into intervals
    for i := 0; i <= n; i++ {
        left := i - ranges[i]
        if left < 0 {
            left = 0
        }

        right := i + ranges[i]
        if right > n {
            right = n
        }

        if right > maxReach[left] {
            maxReach[left] = right
        }
    }

    tapsUsed := 0
    currentEnd := 0
    farthest := 0

    for i := 0; i <= n; i++ {
        if i > farthest {
            return -1
        }

        if maxReach[i] > farthest {
            farthest = maxReach[i]
        }

        if i == currentEnd {
            if currentEnd != n {
                tapsUsed++
                currentEnd = farthest

                if currentEnd >= n {
                    return tapsUsed
                }
            }
        }
    }

    if n == 0 {
        return 0
    }

    return -1
}

The Go implementation follows the exact same greedy logic as the Python version.

Slices are used instead of Python lists. Integer overflow is not a concern because all values remain within small bounds. Since Go does not have built-in max, comparisons are performed manually using if statements.

Worked Examples

Example 1

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

Step 1: Build intervals

Tap	Interval
0	[0,3]
1	[0,5]
2	[1,3]
3	[2,4]
4	[4,4]
5	[5,5]

Step 2: Build max_reach

Left	Farthest Right
0	5
1	3
2	4
4	4
5	5

So:

max_reach = [5,3,4,0,4,5]

Step 3: Greedy traversal

i	farthest	current_end	taps_used	Action
0	5	0	0	reach boundary
0	5	5	1	open tap
0	5	5	1	coverage complete

Answer:

1

Example 2

n = 3
ranges = [0,0,0,0]

Intervals

Tap	Interval
0	[0,0]
1	[1,1]
2	[2,2]
3	[3,3]

max_reach

[0,1,2,3]

Traversal

i	farthest	current_end	Result
0	0	0	boundary reached
1	0	0	i > farthest

Coverage becomes impossible at position 1.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass to build intervals and single greedy scan
Space	O(n)	Uses the max_reach array

The preprocessing loop visits each tap exactly once. The greedy traversal also scans the garden once from left to right. No nested iteration occurs, so the total runtime is linear.

The auxiliary array max_reach requires O(n) extra memory.

Test Cases

from typing import List

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        max_reach = [0] * (n + 1)

        for i in range(n + 1):
            left = max(0, i - ranges[i])
            right = min(n, i + ranges[i])

            max_reach[left] = max(max_reach[left], right)

        taps_used = 0
        current_end = 0
        farthest = 0

        for i in range(n + 1):
            if i > farthest:
                return -1

            farthest = max(farthest, max_reach[i])

            if i == current_end:
                if current_end != n:
                    taps_used += 1
                    current_end = farthest

                    if current_end >= n:
                        return taps_used

        return 0 if n == 0 else -1

sol = Solution()

assert sol.minTaps(5, [3,4,1,1,0,0]) == 1  # single tap covers everything
assert sol.minTaps(3, [0,0,0,0]) == -1  # impossible coverage
assert sol.minTaps(7, [1,2,1,0,2,1,0,1]) == 3  # multiple taps required
assert sol.minTaps(8, [4,0,0,0,0,0,0,0,4]) == 2  # coverage from both ends
assert sol.minTaps(1, [1,1]) == 1  # tiny garden
assert sol.minTaps(1, [0,0]) == -1  # no coverage possible
assert sol.minTaps(5, [5,0,0,0,0,0]) == 1  # first tap covers entire garden
assert sol.minTaps(5, [0,0,0,0,0,5]) == -1  # left side uncovered
assert sol.minTaps(9, [0,5,0,3,3,3,1,4,0,4]) == 2  # overlapping intervals
assert sol.minTaps(2, [0,2,0]) == 1  # middle tap covers everything

Test	Why
n=5, [3,4,1,1,0,0]	Validates optimal single tap coverage
n=3, [0,0,0,0]	Validates impossible coverage detection
n=7, [1,2,1,0,2,1,0,1]	Tests multiple interval chaining
n=8, [4,0,0,0,0,0,0,0,4]	Tests combining large intervals
n=1, [1,1]	Smallest successful garden
n=1, [0,0]	Smallest impossible garden
n=5, [5,0,0,0,0,0]	One interval covers entire garden
n=5, [0,0,0,0,0,5]	Coverage fails near start
n=9, [0,5,0,3,3,3,1,4,0,4]	Complex overlapping intervals
n=2, [0,2,0]	Middle tap dominates all others

Edge Cases

One important edge case occurs when no tap can cover the beginning of the garden. For example:

n = 5
ranges = [0,0,0,0,0,5]

Even though the final tap covers far to the left, it only reaches position 0 if its interval actually extends there. If there is any uncovered gap at the start, the algorithm detects it because the current index eventually becomes larger than farthest.

Another critical case is when a single tap covers the entire garden. For example:

n = 5
ranges = [5,0,0,0,0,0]

The algorithm handles this naturally because the very first interval extends coverage directly to n, allowing an immediate return after one tap.

A third important case involves disconnected intervals. Suppose intervals cover [0,2] and [4,5] but nothing covers position 3. A naive implementation might incorrectly count intervals without checking continuity. This solution explicitly verifies:

i > farthest

which guarantees there are no gaps in coverage.

Finally, heavily overlapping intervals can sometimes confuse greedy implementations that choose intervals too early. This algorithm avoids that issue by delaying tap activation until the current coverage boundary is exhausted, ensuring the farthest possible extension is always selected.