Minimum Number of Taps to Open to Water a Garden — LeetCode 1326 Python Solution
HardGreedyArrayDynamic Programming
- Problem
- #1326
- Pattern
- Greedy
- Reading time
- 3 min
- Source
- leetcode.com
The problem
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n.
Example
- Input
- n = 5, ranges = [3,4,1,1,0,0]
- Output
- 1
- Explanation
- The tap at point 0 can cover the interval [-3,3]
Python solution
Python
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
last = [0] * (n + 1)
for i, x in enumerate(ranges):
l, r = max(0, i - x), i + x
last[l] = max(last[l], r)
ans = mx = pre = 0
for i in range(n):
mx = max(mx, last[i])
if mx <= i:
return -1
if pre == i:
ans += 1
pre = mx
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1326. Minimum Number of Taps to Open to Water a Garden is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1326. Minimum Number of Taps to Open to Water a Garden?
- LeetCode 1326. Minimum Number of Taps to Open to Water a Garden is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1326. Minimum Number of Taps to Open to Water a Garden?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1326. Minimum Number of Taps to Open to Water a Garden?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1326. Minimum Number of Taps to Open to Water a Garden cover?
- LeetCode 1326. Minimum Number of Taps to Open to Water a Garden is tagged Greedy, Array and Dynamic Programming on LeetCode.