Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Linear time solution in Clear category for Garland by amandel
from itertools import accumulate
def illuminate_all(lights: list[int]) -> int:
span=len(lights)*[-1]
for i,l in enumerate(lights):
t=max(i-l,0)
span[t]=max(span[t], i+l)
span=list(accumulate(span,max))
r=0
cnt=0
while r < len(lights):
r = span[r]+1
cnt += 1
return cnt
print("Example:")
print(illuminate_all([0, 0]))
# These "asserts" are used for self-checking
assert illuminate_all([0, 0]) == 2
assert illuminate_all([2, 3, 3, 2]) == 1
assert illuminate_all([1, 0, 1, 0]) == 2
print("The mission is done! Click 'Check Solution' to earn rewards!")
July 5, 2023
Comments:
