Minimum Number of Taps to Open to Water a Garden

Minimum Number of Taps to Open to Water a Garden looks like a hard interval problem, but it is secretly the classic Jump Game II in disguise. The trick is to turn each tap into a single number — how far right it lets you stretch — and then greedily count the fewest hops needed to reach the end.

The slow way first

You could treat each tap as an interval and try every subset of taps to see which combinations cover [0, n] — exponential and hopeless. A smarter but still heavy idea is interval-scheduling DP: sort intervals and compute the minimum taps to cover each prefix in O(n²) or O(n log n).

The question to ask: standing at some covered point, what is the farthest right I can guarantee by opening one more tap? If I always extend as far as possible, I never need to second-guess — that is the greedy that powers Jump Game.

The idea: turn taps into reach, then jump

First, collapse the taps. For each tap with interval [l, r], record that from the left edge l you can stretch all the way to r. Keep the best r per starting position in an array reach, where reach[p] is the farthest right point you can get to if your covered frontier is at p.

Now sweep left to right exactly like Jump Game II. Track cur (the farthest point covered by taps opened so far) and nxt (the best you could reach by opening one more tap somewhere up to cur). Every time the index i catches up to cur, you must commit a tap: bump the count and jump cur forward to nxt.

If you ever reach the frontier and the best next reach does not move you forward (nxt <= i), there is a gap that no tap can bridge — return -1.

Walk through it

Step through the animation. First we build reach = [3, 5, 3, 4, 4, 5] from the taps. Then i sweeps the axis: at i = 0 the best reach is 3, so when i hits the frontier we open tap one and jump cur to 3. Scanning 1..3, position 1 stretches to 5, so when i hits 3 we open a second tap and jump to 5 = n. The garden is covered with 2 taps.

Pseudocode

reach = array of size n+1, all 0
for each tap i with range r:
    l = max(0, i - r);  hi = min(n, i + r)
    reach[l] = max(reach[l], hi)     # from l you can stretch to hi
taps = 0; cur = 0; nxt = 0
for i from 0 to n:
    nxt = max(nxt, reach[i])         # best reach seen up to here
    if i == cur:                     # ran out of the current segment
        if nxt <= i: return -1       # cannot move forward -> gap
        taps += 1                    # commit one more tap
        cur = nxt                    # frontier jumps forward
return taps

The Python solution

def min_taps(n, ranges):
    reach = [0] * (n + 1)
    for i, r in enumerate(ranges):
        lo = max(0, i - r)
        hi = min(n, i + r)
        reach[lo] = max(reach[lo], hi)
    taps = 0
    cur = nxt = 0
    for i in range(n + 1):
        nxt = max(nxt, reach[i])
        if i == cur:
            if nxt <= i:
                return -1
            taps += 1
            cur = nxt
    return taps

• reach[lo] is the farthest right point you can get to once your frontier is at lo; we keep the maximum over all taps that start there.
• cur is the right end of what is covered by the taps opened so far; nxt is the best we could do with one more tap among positions 0..cur.
• The sweep updates nxt at every position, but only acts when i == cur — that is the moment we are forced to open a tap.
• if nxt <= i catches a gap: the frontier cannot advance, so the garden is uncoverable and we return -1.
• Each i == cur event costs exactly one tap, so taps ends as the minimum.

Complexity

We do two linear passes and store one reach array, so the whole thing is O(n) time and O(n) space — the same shape as Jump Game II.

When this pattern shows up

Practice