Show problems as
Classic problem #1326HardArrayDynamic ProgrammingGreedy

Minimum Number of Taps to Open to Water a Garden

Real-world version: Fewest Lamps to Light the Corridor
Tracked in this browser only
Read Minimum Number of Taps to Open to Water a Garden on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_taps(n: int, spread: list[int]) -> int:
Java
public int minTaps(int n, int[] spread)

More on the same topics