Minimum Number of Taps to Open to Water a Garden LeetCode solution in Python

1
class Solution:
2
    def minTaps(self, n: int, ranges: List[int]) -> int:
3
        max_range = [0] * (n + 1)
4

5
        for i, r in enumerate(ranges):
6
            left, right = max(0, i - r), min(n, i + r)
7
            max_range[left] = max(max_range[left], right - left)
8

9
        # it's a jump game now
10
        start = end = step = 0
11

12
        while end < n:
13
            step += 1
14
            start, end = end, max(i + max_range[i] for i in range(start, end + 1))
15
            if start == end:
16
                return -1
17

18
        return step