from typing import List
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
# find intervals starting from different locations
intervals = []
for center, width in enumerate(ranges):
# if the element is 0, then this element is useless
if width != 0:
# restrict the interval in [0, n]
interval = [max(0, center - width), min(center + width, n)]
intervals.append(interval)
# if every element is 0, then return -1
if not intervals:
return -1
# find the furthest location it can reach from a current location
d = {}
for interval in intervals:
if interval[0] not in d:
d[interval[0]] = []
d[interval[0]].append(interval[1])
for k in d:
d[k] = max(d[k])
# current location
loc = 0
# result
res = 0
# if it doesn't reach the furthest location (n)
while loc != n:
# find the furthest location (max(...)) it can reach (<= d[k]) from our position (k)
maxLocation = -1
s = set()
for k in d:
if k <= loc:
s.add(k)
maxLocation = max(maxLocation, d[k])
if maxLocation == -1:
return -1
# delete every element we iterate previously (we won't search elements again)
for k in s:
del d[k]
res += 1
loc = maxLocation
return res
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)