Minimum Number of K Consecutive Bit Flips

HARD

Description

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⁵
1 <= k <= nums.length

Approaches

Checkout 3 different approaches to solve Minimum Number of K Consecutive Bit Flips. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: O(N). A single pass through the array is performed.Space Complexity: O(1). We only use a few variables for tracking state and modify the input array in-place.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Number of K Consecutive Bit Flips. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Minimum Number of K Consecutive Bit Flips

Patterns:

Sliding WindowBit ManipulationPrefix Sum

Data Structures:

ArrayQueue

Companies:

thoughtspot |