Bulb Switcher III

Problem Id: 1375 Difficulty: Medium Tag: Array


Intuition

We could use a heap to solve this problem.

If at moment t, all bulbs are blue. Then the bulbs must be from 1 to t. We use a heap to save the bulbs which has been truned on. And each time, we try to remove bulbs from the heap in order. If any bulb is missing, for example, last bulb we poped is 3, but the top of the heap is 5, then 4 is missed, we stop the pop process. If at any moment the heap could be poped to empty, it means all bulbs are continues, so all bulbs are blue.

Solution


import heapq


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_light = 0
        heap = []
        all_blue_count = 0
        for i in light:
            heapq.heappush(heap, i)
            while heap and heap[0] == max_light + 1:
                heapq.heappop(heap)
                max_light += 1
            if not heap:
                all_blue_count += 1
        return all_blue_count