584. Garden Sprinklers
A long straight flower bed runs from position 0 to position n along a path. A sprinkler is installed at every integer position i from 0 to n (that is n + 1 sprinklers), and the sprinkler at i sprays every point in the closed interval [i - ranges[i], i + ranges[i]]. A range of 0 waters only its own spot. Sprays may extend past either end of the bed.
The gardener may switch on any subset of sprinklers. Return the minimum number that must be switched on so that every point of the bed [0, n] gets water, or -1 if no choice of sprinklers can do it. The intended solution runs in O(n) time and O(n) space.
Example 1
- Input:
- n = 6, ranges = [2,1,0,1,0,0,3]
- Output:
- 3
- Explanation:
Sprinklers 0 (covers up to 2), 3 (covers 2 to 4) and 6 (covers 3 to 6 and beyond) together water the whole bed, and two cannot.
Example 2
- Input:
- n = 4, ranges = [0,0,0,0,0]
- Output:
- -1
- Explanation:
Every sprinkler only waters its own spot, so the stretches between them stay dry and the answer is -1.
Example 3
- Input:
- n = 5, ranges = [1,0,4,0,0,2]
- Output:
- 1
- Explanation:
The sprinkler at position 2 sprays from -2 to 6, which already covers the entire bed.
Constraints
- 1 ≤ n ≤ 105
- ranges.length == n + 1
- 0 ≤ ranges[i] ≤ 100
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)