0374HardArrayDynamic ProgrammingGreedy

Fewest Lamps to Light the Corridor

Tracked in this browser only

Trains the technique from

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

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A corridor runs from position 0 to position n. A lamp is fitted at every whole position from 0 through n, so there are n + 1 of them, and spread[i] says how far lamp i throws light: switched on, it lights the whole closed stretch from i - spread[i] to i + spread[i]. A lamp with a spread of 0 lights nothing at all, not even the point it hangs over.

Light spilling past position 0 or past position n is simply wasted.

Return the fewest lamps that can be switched on so that every point of the corridor from 0 to n is lit, or -1 if no combination of lamps manages it.

Examples

Example 1

Input: n = 6, spread = [0,3,0,0,0,2,0]
Output: 2

Lamp 1 lights positions 0 through 4 once the spill below 0 is discarded, and lamp 5 lights positions 3 through 6. Together they cover the whole corridor with two lamps.

Example 2

Input: n = 8, spread = [4,0,0,0,4,0,0,0,4]
Output: 1

Lamp 4 lights positions 0 through 8 on its own.

Example 3

Input: n = 4, spread = [0,0,0,0,0]
Output: -1

Every lamp has a spread of 0, so nothing is ever lit.

Example 4

Input: n = 5, spread = [2,0,0,0,0,2]
Output: -1

Lamp 0 reaches up to position 2 and lamp 5 reaches down to position 3, so the stretch between 2 and 3 stays dark whatever is switched on.

Constraints

1 <= n <= 10^4
spread.length == n + 1
0 <= spread[i] <= 100

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_taps(n: int, spread: list[int]) -> int:

Java

public int minTaps(int n, int[] spread)

The intended approach

Time O(n)Space O(n) for the reach table

Turn each lamp into the stretch it lights, clipped to the corridor, and for every left edge keep only the furthest right edge reachable from it, since a shorter stretch starting at the same place is never worth using. Then sweep: hold the position lit so far, scan every left edge up to it while noting the furthest right edge any of them reaches, and jump the lit position out to that furthest edge, counting one lamp. If the scan finds nothing beyond the current lit position the corridor cannot be finished.

Pythonentry point: min_taps

def min_taps(n, spread):
    # For every left edge keep the furthest right edge any lamp reaches from it,
    # then sweep the corridor once. Time O(n), space O(n) for the reach table.
    reach = [0] * (n + 1)
    for i in range(n + 1):
        r = spread[i]
        if r == 0:
            continue
        left = i - r
        if left < 0:
            left = 0
        right = i + r
        if right > n:
            right = n
        if right > reach[left]:
            reach[left] = right
    lit = 0
    furthest = 0
    count = 0
    cursor = 0
    while lit < n:
        while cursor <= lit:
            if reach[cursor] > furthest:
                furthest = reach[cursor]
            cursor += 1
        if furthest <= lit:
            return -1
        lit = furthest
        count += 1
    return count

The obvious version

Treat each right edge as a state holding the fewest lamps needed to light everything up to it, start from edge 0, and relax with every lamp whose stretch starts no later than that edge and finishes strictly beyond it.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_taps(n, spread):
    big = float("inf")
    best = [big] * (n + 1)
    best[0] = 0
    for edge in range(n + 1):
        if best[edge] == big:
            continue
        for i in range(n + 1):
            r = spread[i]
            if r == 0:
                continue
            left = i - r
            right = i + r
            if right > n:
                right = n
            if left <= edge and right > edge and best[edge] + 1 < best[right]:
                best[right] = best[edge] + 1
    return -1 if best[n] == big else best[n]

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in