Minimum Number of Taps to Open to Water a Garden
Hard · Greedy · Array · Dynamic Programming · Greedy
Problem
A garden lies along a line from point 0 to point n. There is a tap at every whole point 0, 1, ..., n, so n + 1 taps in all.
Tap i, when opened, waters the stretch [i - ranges[i], i + ranges[i]]. A range of 0 waters only the point the tap stands on.
Return the fewest taps to open so that the whole garden [0, n] is watered, or -1 if that is impossible. Watering every whole point is not enough: the stretches must leave no gap anywhere in between.
Examples
Input: n = 6, ranges = [1,0,3,0,0,2,0] Output: 2
Tap 2 waters [-1, 5] and tap 5 waters [3, 7]. No single tap covers [0, 6].
Input: n = 4, ranges = [0,1,0,0,0] Output: -1
Tap 1 waters [0, 2]. Nothing waters the stretch from 2 to 4.
Input: n = 5, ranges = [5,0,0,0,0,0] Output: 1
Tap 0 waters [-5, 5], which includes the whole garden.
Constraints
- 1 <= n <= 10^4
- len(ranges) == n + 1
- 0 <= ranges[i] <= 100
Approaches
- Baseline: DP over points, every tap at every point — time O(n · R), space O(n)
Follow-up
This is the same as covering a segment with the fewest intervals, and the same scan solves "fewest jumps to the end of an array". If each tap also had a price and you wanted the cheapest cover, the greedy no longer works: use the DP over points, or Dijkstra over the points with taps as edges.
Related problems
Start free on Cariara · Coding problems · System design studio
