Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Stack + sorting solution O(N*log(N)) solution in Speedy category for Garland by swagg010164
def illuminate_all(lights: list[int]) -> int:
arr = []
for ind, l in enumerate(lights):
arr.append((max(0, ind - l), min(len(lights) - 1, ind + l), ind))
arr.sort(key=lambda x: x[1])
stack = []
for ind in range(len(arr)):
while stack and stack[-1][0] >= arr[ind][0]:
stack.pop()
if not stack or stack[-1][1] < arr[ind][1]:
if len(stack) > 1 and \
stack[-2][0] <= stack[-1][0] <= stack[-2][1] and \
arr[ind][0] <= stack[-1][1] <= arr[ind][1] and \
arr[ind][0] <= stack[-2][1] + 1:
stack.pop()
stack.append(arr[ind])
return len(stack)
Aug. 11, 2023
