MANG Problem #37: Minimum Number of K Consecutive Bit Flips (Hard)

1. Problem Statement

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

2. Approach: Sliding Window + Flip Tracking

The naive approach is to physically flip $K$ bits every time we see a 0. This takes $O(N \times K)$ time.

To achieve $O(N)$, we must avoid physical flips. Instead, we track the number of flips applied to the current index.

If a bit has been flipped an even number of times, its value hasn't changed.
If it has been flipped an odd number of times, its value is toggled.

We maintain a currentFlips counter and an array isFlipped to track when a previous flip's effect "expires" (falls out of the sliding window).

3. Java Implementation

public int minKBitFlips(int[] nums, int k) {
    int n = nums.length;
    int[] isFlipped = new int[n];
    int currentFlips = 0;
    int totalFlips = 0;

    for (int i = 0; i < n; i++) {
        // If a past flip's window has passed, remove its effect
        if (i >= k) {
            currentFlips ^= isFlipped[i - k]; // XOR to subtract the flip
        }

        // If the current bit (considering flips) is 0, we MUST flip it
        if (currentFlips % 2 == nums[i]) {
            // We can't flip if there's no room for a k-length window
            if (i + k > n) return -1;
            
            isFlipped[i] = 1; // Mark that a flip started here
            currentFlips ^= 1; // Increase active flips
            totalFlips++;
        }
    }
    return totalFlips;
}

4. 5-Minute "Video-Style" Walkthrough

The Greedy Choice: We iterate from left to right. If nums[i] (after applying past flips) is 0, we must start a flip at i. There is no other choice, because we can't go back.
The Virtual Flip: currentFlips tracks how many active flips cover our current index. We XOR it by 1 to simulate a flip.
The Window Expiration: A flip started at index x affects exactly $K$ elements. When we reach index x + k, that flip no longer affects us. We use isFlipped[i-k] to "un-apply" the expired flip.

5. Interview Discussion