Minimum Number of K Consecutive Bit Flips: Greedy Sliding Window

LeetCode Minimum Number of K Consecutive Bit Flips (Problem 995) asks you to find the minimum number of flips needed to make every element of a binary array equal to 1. Each flip operation selects exactly k consecutive elements and toggles each one (0 becomes 1, 1 becomes 0). If it is impossible to make every element 1, you return -1.

Why this problem matters

This problem sits at the intersection of greedy algorithms, sliding windows, and bit manipulation. It forces you to think about how flip operations compose and overlap. The naive approach of trying every possible sequence of flips is exponential, but a greedy observation collapses the search space entirely. Problems like this train your instinct for spotting when a greedy choice is provably optimal, a skill that transfers to many other array and interval problems.

The key insight

If the leftmost element is 0, you have no choice: you must flip the window starting at that position. No later flip can fix it without re-flipping something you already handled to the left. This means you can scan left to right, and whenever you encounter a 0 (after accounting for all previous flips), you must flip starting at that index. If flipping would extend past the end of the array, the answer is -1.

The greedy choice is forced at every step. You never have a reason to delay a flip or choose a different starting position. The only question is whether the remaining array is long enough to fit a window of size k.

The tricky part is tracking the cumulative effect of overlapping flips efficiently. Instead of actually flipping k elements each time (which would give O(nk) time), you can use a difference array or a queue to record where flips start and end. At each index, you know how many times it has been flipped by checking a running count. If the running count is even, the bit is in its original state. If odd, it has been toggled.

The solution

from collections import deque

def minKBitFlips(nums, k):
    n = len(nums)
    flip_queue = deque()
    flips = 0

    for i in range(n):
        if flip_queue and flip_queue[0] == i:
            flip_queue.popleft()

        if (len(flip_queue) % 2) == nums[i]:
            if i + k > n:
                return -1
            flip_queue.append(i + k)
            flips += 1

    return flips

The flip_queue tracks the endpoints of active flip windows. When you reach index i, any flip that started at i - k + 1 or earlier has already expired, so you pop it from the front. The current effective value of nums[i] depends on how many active flips cover it: if the count is even, the value is unchanged, and if odd, it is toggled. The condition (len(flip_queue) % 2) == nums[i] checks whether the effective value at index i is 0. When nums[i] is 0 and the flip count is even, the effective value is still 0, so you need to flip. When nums[i] is 1 and the flip count is odd, it has been toggled to 0, so you also need to flip.

Visual walkthrough

The walkthrough uses nums = [0, 0, 0, 1, 0, 1, 1, 0] with k = 3. The greedy scan finds three forced flips: at index 0, index 4, and index 5. After all three, every element is 1. Notice how flipping at index 4 toggles indices 5 and 6 from 1 to 0, which the next flip at index 5 then corrects. Overlapping flips are normal and expected.

Complexity analysis

Each index is visited exactly once in the main loop. The queue operations (append and popleft) are O(1) amortized. The queue holds at most n / k entries at any given time, but in the worst case it could accumulate up to O(n) entries total across the entire run. So the time complexity is O(n) and the space complexity is O(n).

You can also implement this with a difference array instead of a queue. Allocate an array of size n, mark the start and end of each flip, and maintain a running prefix sum to know the current flip count at each index. This also achieves O(n) time and O(n) space, but the queue-based approach is slightly cleaner to write.

The building blocks

1. Greedy left-to-right forcing

The core technique is recognizing that the leftmost unsatisfied constraint forces your hand. You cannot fix a 0 at position i with any flip that starts after i, because such a flip would not reach i. This "forced move" argument is what makes greedy correct. You will see this pattern in other problems where local constraints propagate from one end to the other, such as the candy distribution problem or gas station circuit.

2. Flip tracking with a sliding window

Instead of performing each flip in O(k) time, you track the net effect of all overlapping flips using a queue (or difference array). The queue stores the endpoints where flips expire, and the length of the queue tells you how many flips are currently active. This transforms the problem from O(nk) to O(n). The same "lazy propagation" idea appears in range update problems, segment trees, and other contexts where you need to apply many overlapping operations efficiently.

Edge cases

All elements are already 1. No flips are needed. The algorithm scans through without ever triggering a flip, and returns 0.

Single 0 at the end with k greater than 1. If the only 0 is at position n - 1 and k is 2 or more, flipping at n - 1 would extend past the array. The algorithm correctly returns -1.

Alternating 0s and 1s. This creates many overlapping flips. Each flip toggles previously corrected bits, causing cascading flips. The greedy approach handles this correctly because it always checks the effective value after accounting for all active flips.

k equals 1. Every element can be flipped independently. The answer is simply the count of 0s in the array. The algorithm degenerates to checking each element individually.

k equals n. You can only flip the entire array at once. The answer is 0 if all elements are 1, 1 if all elements are 0, and -1 otherwise (since a single full-array flip toggles everything, and you cannot selectively fix individual positions).

From understanding to recall

The hardest part of this problem is not the code. It is convincing yourself that greedy works. The key argument to internalize is this: the leftmost 0 can only be fixed by a flip starting at that exact position. Once you own that insight, the rest follows naturally.

When reviewing this problem, focus on two things. First, practice articulating why the greedy choice is forced (not just optimal). Second, make sure you can explain the flip tracking mechanism. The queue stores expiration points, not start points. The length of the queue gives you the active flip count. If you can reconstruct both the greedy argument and the tracking mechanism from memory, you have this problem locked in.

Also watch for the connection to difference arrays. The queue-based approach is essentially a difference array in disguise: you record where effects begin and end, and derive the current state from a running count. This pattern shows up repeatedly in range update and interval scheduling problems.

Related posts

• Sliding Window Maximum - Another sliding window problem where you track active elements using a deque. The mechanics of adding and expiring elements are similar to the flip queue here.
• Minimum Size Subarray Sum - A classic sliding window problem. While it does not involve bit flips, the technique of maintaining a window that grows and shrinks as you scan left to right is the same foundational pattern.
• Subarray Sum Equals K - Uses prefix sums to efficiently query subarray properties. The difference array technique for tracking flips is a close relative of the prefix sum approach used here.