Minimum Number of K Consecutive Bit Flips

Minimum Number of K Consecutive Bit Flips is a classic greedy problem. The naive simulation is too slow, but a single left-to-right sweep with a difference array turns it into clean O(n) — and it teaches the trick of tracking flip parity instead of actually flipping bits.

The slow way first

The obvious idea: scan left to right, and whenever you see a 0, flip the window of k bits starting there. That greedy choice is correct, but if you actually flip every bit in the window each time, one operation costs O(k), so the whole thing is O(n·k) — too slow when both are large.

The question to ask: do I really need to flip the bits, or just know the result? All I care about at position i is the bit's current value after every earlier flip. If I can compute that in O(1), I never touch the window contents at all.

The idea: track flip parity with a difference array

Each flip window only matters as parity — an even number of flips covering a position cancels out, an odd number flips it. So keep a running parity. The effective bit at i is nums[i] XOR parity.

When a flip starts at i, toggle parity and record that this flip ends at i + k by marking diff[i + k]. As the sweep reaches each index, first apply any pending expirations (parity ^= diff[i]) so windows automatically stop covering once they run out.

Greedy correctness: the leftmost effective 0 can only be fixed by a window that starts at i (any earlier start is already past, any later start cannot reach back). So that flip is forced — no choice, no backtracking.

Walk through it

Step through the animation. The pointer i scans left to right. The parity label tracks the running flip count mod 2. At i = 0 the effective bit is 0, so we flip [0, 2). At i = 1 parity is still 1, the effective bit is again 0, so we flip [1, 3). At i = 2 the first window expires (diff[2]), parity returns to 1, the effective bit is 1, and we are done with 2 flips.

Pseudocode

diff = array of zeros, length n + 1   # diff[j] marks a flip window ending at j
flips = 0
parity = 0
for i from 0 to n - 1:
    parity ^= diff[i]                  # expire any window that ended here
    if (nums[i] XOR parity) == 0:      # effective bit is 0 -> must fix it
        if i + k > n:
            return -1                  # window would run off the end
        flips += 1
        parity ^= 1                    # this flip now covers forward
        diff[i + k] ^= 1               # ...until index i + k
return flips

The Python solution

def min_k_bit_flips(nums, k):
    n = len(nums)
    diff = [0] * (n + 1)
    flips = parity = 0
    for i in range(n):
        parity ^= diff[i]
        if (nums[i] ^ parity) == 0:
            if i + k > n:
                return -1
            flips += 1
            parity ^= 1
            diff[i + k] ^= 1
    return flips

• diff is the difference array: diff[j] = 1 means a flip window ends just before index j.
• parity ^= diff[i] refreshes the running parity by expiring any window that ended at i.
• nums[i] ^ parity is the effective bit — the real value after all flips so far, computed in O(1).
• If that effective bit is 0, we are forced to flip here. i + k > n means the window spills past the end, which is impossible, so we return -1.
• Flipping is recorded, not performed: toggle parity now and diff[i + k] so the window auto-expires later.

Complexity

We trade O(n) extra space (the diff array) for the speed win: O(n·k) to O(n). The diff array can be replaced by a sliding-window counter for O(1) space, but the parity idea is the same.

When this pattern shows up

Practice