Minimum Number of K Consecutive Bit Flips

---

Minimum Number of K Consecutive Bit Flips: 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 <= 10^5
• 1 <= k <= nums.length

---

Try this Problem on your own or check similar problems:

1. Bulb Switcher
2. Minimum Time to Remove All Cars Containing Illegal Goods

Solution:

Java

public int minKBitFlips(int[] nums, int k) {
    Deque<Integer> flipQueue = new ArrayDeque<>();
    int result = 0;

    for (int i = 0; i < nums.length; ++i) {
        if ((nums[i] == 0 && flipQueue.size() % 2 == 0) || (nums[i] == 1 && flipQueue.size() % 2 == 1)) {
            ++result;
            if (i + k > nums.length) return -1;
            flipQueue.add(i + k - 1);
        }
        if (!flipQueue.isEmpty() && flipQueue.peek() == i) {
            flipQueue.pop();
        }
    }
    return result;
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minKBitFlips = function (nums, k) {
  const flipQueue = [];
  let result = 0;

  for (let i = 0; i < nums.length; i++) {
    if (
      (nums[i] === 0 && flipQueue.length % 2 === 0) ||
      (nums[i] === 1 && flipQueue.length % 2 === 1)
    ) {
      result++;
      if (i + k > nums.length) return -1;
      flipQueue.push(i + k - 1);
    }
    if (flipQueue.length > 0 && flipQueue[0] === i) {
      flipQueue.shift();
    }
  }
  return result;
};

Python

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        flipQueue = deque()
        result = 0

        for i in range(len(nums)):
            if (nums[i] == 0 and len(flipQueue) % 2 == 0) or (nums[i] == 1 and len(flipQueue) % 2 == 1):
                result += 1
                if i + k > len(nums):
                    return -1
                flipQueue.append(i + k - 1)
            if len(flipQueue) > 0 and flipQueue[0] == i:
                flipQueue.popleft()

        return result

C++

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        deque<int> flipQueue;
        int result = 0;

        for (int i = 0; i < nums.size(); i++) {
            if ((nums[i] == 0 && flipQueue.size() % 2 == 0) || (nums[i] == 1 && flipQueue.size() % 2 == 1)) {
                result++;
                if (i + k > nums.size()) return -1;
                flipQueue.push_back(i + k - 1);
            }
            if (!flipQueue.empty() && flipQueue.front() == i) {
                flipQueue.pop_front();
            }
        }
        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(k)

---

Explanation:

In this problem, we want to determine the minimum number of flips required to make all elements in the array 1s. We can do this by following a greedy strategy: whenever we see a 0, we flip it and the next k-1 elements to 1. This way, we ensure that every 0 is flipped to a 1.

To keep track of the number of flips required at each index, we can use a deque to store the indices where the last flip ends. For example, if the current flip starts at index 3 and ends at index 8, we will add 8 to the queue. As we continue iterating through the array, we remove the head of the queue whenever we reach the end of a flip. This way, we can determine the number of flips that have occurred at any given index by checking the length of the queue.

We can then use this information to decide whether to flip a given element. If the element is a 0 and the number of flips is even (e.g we have 0 and flip it 2 times we will still get a 0, 0 -> 1 -> 0, so we need to flip it again), or if the element is a 1 (we have 1 and we flip it one time 1 - 0 we will have 0 and we need to flip it again) and the number of flips is odd, we need to flip it. Otherwise, we can skip it.

Finally, if at any point the last index of the current flip is greater than the length of the array, we return -1 since it is not possible to achieve the desired result. Otherwise, we return the total number of flips required.

We need a deque with max size of k so the space complexity is O(k) (since we're tracking at most ends of k intervals, e.g. k=3 you can only have 3 elements in the deque, since at index = 2 we will remove the end of the first interval that start at the first element), while we have linear time complexity since we iterate over the whole input array.