# Minimum Number of K Consecutive Bit Flips
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-k-consecutive-bit-flips
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Queue
**Companies:** [thoughtspot](https://scaleengineer.com/companies/thoughtspot)
---
## Problem
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`.

A **subarray** is a **contiguous** part of an array.

**Example 1:**

**Input:** nums = [0,1,0], k = 1
**Output:** 2
**Explanation:** Flip nums[0], then flip nums[2].

**Example 2:**

**Input:** nums = [1,1,0], k = 2
**Output:** -1
**Explanation:** No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].

**Example 3:**

**Input:** nums = [0,0,0,1,0,1,1,0], k = 3
**Output:** 3
**Explanation:** 
Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= k <= nums.length`

# Approaches
## Brute-Force Simulation
This approach directly simulates the greedy strategy. We iterate through the array, and whenever we encounter a `0`, we perform a k-bit flip on the subarray starting at that position.
**Time:** O(N * K). The outer loop runs up to `N` times, and for each time we decide to flip, the inner loop runs `K` times. In the worst case, this is O(N*K). · **Space:** O(1), as we modify the input array in-place and use only a few extra variables.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large `N` and `K`, likely to result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The core idea is that to make the array all `1`s, we must process it from left to right. If `nums[i]` is `0`, the only way to change it to `1` is by performing a flip on the subarray `nums[i...i+k-1]`. Any flip starting at an index greater than `i` will not affect `nums[i]`. Therefore, we have no choice but to flip at `i`. This greedy choice is optimal.

The algorithm iterates from `i = 0` to `n-k`. If `nums[i]` is `0`, it increments a flip counter and then explicitly flips all `k` bits in the subarray `nums[i...i+k-1]`. After this loop, it checks the last `k-1` elements. If any of them are `0`, it's impossible to make them `1` because any flip would extend beyond the array's bounds. In this case, we return `-1`. Otherwise, the accumulated count is the minimum number of flips.

```java
class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int flips = 0;

        for (int i = 0; i <= n - k; i++) {
            if (nums[i] == 0) {
                flips++;
                for (int j = 0; j < k; j++) {
                    nums[i + j] = 1 - nums[i + j];
                }
            }
        }

        // Check if the remaining part of the array is all 1s
        for (int i = n - k + 1; i < n; i++) {
            if (nums[i] == 0) {
                return -1;
            }
        }

        return flips;
    }
}
```
### Algorithm
- Initialize `flips = 0`.
- Iterate `i` from `0` to `nums.length - k`.
- If `nums[i]` is `0`:
  - Increment `flips`.
  - Iterate `j` from `i` to `i + k - 1`.
  - Flip `nums[j]` (e.g., `nums[j] = 1 - nums[j]`).
- Iterate `i` from `nums.length - k + 1` to `nums.length - 1`.
- If `nums[i]` is `0`, return `-1`.
- Return `flips`.

## Sliding Window with a Queue
This approach optimizes the simulation by avoiding the O(K) work for each flip. Instead of actually flipping the subarray, we keep track of the "flip effect" on the current element using a sliding window.
**Time:** O(N). We iterate through the array once. Each index is added to and removed from the queue at most once, leading to amortized O(1) time for queue operations per element. · **Space:** O(K). The queue can hold at most `K` indices, representing the flips active in the current window.
**Pros:** Efficient time complexity, making it suitable for large inputs.; The logic is a clear improvement over the brute-force method.
**Cons:** Uses extra space proportional to `K`, which can be large.
### Explanation
We still follow the same greedy strategy of iterating from left to right. At any index `i`, the actual value of the bit is `original_nums[i]` flipped by all active flip operations. An active flip is one that started at an index `j` such that `i` is in the range `[j, j+k-1]`.

We can use a queue to store the starting indices of these active flips. The size of the queue tells us how many times the current element `i` has been flipped. The algorithm iterates from `i = 0` to `n-1`. At each `i`, we first remove indices `j` from the front of the queue if their flip window has ended (i.e., `j <= i - k`). The current number of active flips is the queue's size. We determine the effective bit value: `(nums[i] + queue.size()) % 2`. If this effective value is `0`, we must perform a flip. We check if `i + k <= n`. If not, it's impossible, so we return `-1`. Otherwise, we increment our total flip count and add `i` to the queue.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int flips = 0;
        Queue<Integer> flipQueue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // Remove flips that are no longer active
            if (!flipQueue.isEmpty() && flipQueue.peek() <= i - k) {
                flipQueue.poll();
            }

            int currentFlips = flipQueue.size();
            
            // Determine the effective value of nums[i]
            if ((nums[i] + currentFlips) % 2 == 0) {
                if (i + k > n) {
                    return -1;
                }
                flips++;
                flipQueue.add(i);
            }
        }

        return flips;
    }
}
```
### Algorithm
- Initialize `flips = 0`.
- Initialize a queue `flipQueue` to store indices where flips start.
- Iterate `i` from `0` to `nums.length - 1`.
- While `flipQueue` is not empty and `flipQueue.peek() <= i - k`, remove the front element.
- The number of active flips is `flipQueue.size()`.
- The effective value of `nums[i]` is `(nums[i] + flipQueue.size()) % 2`.
- If the effective value is `0`:
  - If `i + k > nums.length`, return `-1`.
  - Increment `flips`.
  - Add `i` to `flipQueue`.
- Return `flips`.

## Optimal Constant Space Solution
This is the most efficient approach, achieving linear time complexity with constant extra space. It cleverly uses the input array itself to store information about ongoing flips, eliminating the need for an auxiliary data structure like a queue.
**Time:** O(N). A single pass through the array is performed. · **Space:** O(1). We only use a few variables for tracking state and modify the input array in-place.
**Pros:** Most efficient solution in both time and space.; Achieves the optimal O(1) space complexity.
**Cons:** The logic is more subtle due to the in-place modification of the array to store state.; Modifies the input array, which might not be permissible in all contexts.
### Explanation
The logic is similar to the sliding window approach, but instead of a queue, we use a single variable, `current_flip_effect`, to track the parity (even or odd) of active flips. We iterate from `i = 0` to `n-1`. At each step `i`, we need to know if `current_flip_effect` should change. A change occurs if a flip window that started `k` positions ago is now ending. To signal this, when we decide to flip at an index `j`, we modify `nums[j]` to a value other than 0 or 1 (e.g., by adding 2). This acts as a marker. When we reach index `i`, we first check `nums[i-k]` (if `i >= k`). If it's marked, we know a flip started at `i-k` and its effect ends here, so we update `current_flip_effect`. Then, we determine the effective value of `nums[i]` using its original value and `current_flip_effect`. If a flip is needed, we update `current_flip_effect`, increment the total flip count, and mark `nums[i]` to signal the start of a new flip.

```java
class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int flips = 0;
        int currentFlipEffect = 0; // 0 for even flips, 1 for odd flips

        for (int i = 0; i < n; i++) {
            // A flip started at i-k is no longer active
            if (i >= k && nums[i - k] > 1) {
                currentFlipEffect ^= 1;
            }

            // Check if the current bit needs to be flipped
            // (nums[i] + currentFlipEffect) % 2 == 0 is equivalent to nums[i] == currentFlipEffect
            if (nums[i] == currentFlipEffect) {
                // If we need to flip but can't, it's impossible
                if (i + k > n) {
                    return -1;
                }
                // Perform a flip
                flips++;
                currentFlipEffect ^= 1;
                // Mark that a flip started at this index
                nums[i] += 2;
            }
        }

        return flips;
    }
}
```
### Algorithm
- Initialize `flips = 0` and `current_flip_effect = 0`.
- Iterate `i` from `0` to `nums.length - 1`.
- If `i >= k` and `nums[i-k] > 1`, it means a flip started at `i-k`. Its effect is now over, so we toggle `current_flip_effect`.
- The current effective bit is `(nums[i] + current_flip_effect) % 2`.
- If this effective bit is `0`:
  - If `i + k > nums.length`, return `-1`.
  - Increment `flips`.
  - Toggle `current_flip_effect`.
  - Mark `nums[i]` by adding 2 to it, to signal that a flip started here.

# Solutions
### Java

```java
class Solution {
public
  int minKBitFlips(int[] nums, int k) {
    int n = nums.length;
    int[] d = new int[n + 1];
    int ans = 0, s = 0;
    for (int i = 0; i < n; ++i) {
      s += d[i];
      if (nums[i] % 2 == s % 2) {
        if (i + k > n) {
          return -1;
        }
        ++d[i];
        --d[i + k];
        ++s;
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minKBitFlips(vector<int> &nums, int k) {
    int n = nums.size();
    int d[n + 1];
    memset(d, 0, sizeof(d));
    int ans = 0, s = 0;
    for (int i = 0; i < n; ++i) {
      s += d[i];
      if (s % 2 == nums[i] % 2) {
        if (i + k > n) {
          return -1;
        }
        ++d[i];
        --d[i + k];
        ++s;
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int: n = len(nums) d = [0] * (n + 1) ans = s = 0 for i, x in enumerate(nums): s += d[i] if x % 2 == s % 2: if i + k > n: return - 1 d[i] += 1 d[i + k] -= 1 s += 1 ans += 1 return ans

```