Leetcode 995 - Minimum Number of K Consecutive Bit Flips [24/6/24]

Time Taken: More than 1hr
Tag: LeetCode Hard
Basic ideas:
- As we iterate through the nums vector, if current value is 0, we greedily bit flip k consecutive values from current index such that current value is 1
- How do we keep track of the number of bit flips that has affected current index:
- Use “queue” data structure to keep track of indexes before current index that had bit flip.
- For current index, due to question’s requirement of “k consecutive bit flips”, only indexes as early as “current index - k + 1” could have contributed to the number of bit flips that current index has.
- Therefore, we pop indexes less than “current index - k + 1” from queue.
- Remaining size of queue is the number of bit flips affecting current index.
- Taking into consideration the original value at nums[currentIndex], as well as the number of bit flips that affected current index, determine if current index requires a bit flip.
- Case 1 -- No need bit flip: continue to next index.
- Case 2 -- Need bit flip: increment “ans”, add current index to queue.