Code Logo

Minimum K Consecutive Bit Flips

Published at25 Jul 2026
Created by
Hard 0 views
Like0

Given a binary array nums (containing only 0s and 1s) and an integer k, you can flip k consecutive bits in one operation. A flip changes 0 to 1 and 1 to 0. Find the minimum number of operations required to make all elements in the array equal to 1. If it is impossible, return -1.

The key insight uses a greedy approach combined with a sliding window to track flips. As we traverse from left to right, if the current bit is 0 (after considering previous flips that affect it), we must flip at this position because no future flip can affect this bit.

Use a queue or window to track the positions where flips were made. A bit at position i is flipped if the number of flips in the window [i-k+1, i] is odd. This can be tracked with a counter. Each time we flip, we add the current position to the window and increment the counter.

Time complexity is O(n) and space is O(k) for the window tracking. The greedy approach works because once we pass a position, no future operation can affect it, so we must decide immediately whether to flip at that position.

Edge cases include an already all-ones array (return 0), k=1 where each zero requires one flip, and cases where k is larger than the remaining array length making certain positions impossible to fix.

Example Input & Output

Example 1
Input
[0,0,1],1
Output
2
Explanation

Flip index 0 and index 1

Example 2
Input
[1,1,1],2
Output
0
Explanation

Already all ones

Example 3
Input
[0,0,0,1,0,1,1,0],3
Output
3
Explanation

Minimum flips needed is 3

Example 4
Input
[0,0,0],2
Output
-1
Explanation

Impossible to make all ones

Example 5
Input
[0,1,0],1
Output
2
Explanation

Flip index 0 then index 2

Algorithm Flow

Recommendation Algorithm Flow for Minimum K Consecutive Bit Flips
Recommendation Algorithm Flow for Minimum K Consecutive Bit Flips

Solution Approach

<p>function minKBitFlips(nums, k) {
  var n = nums.length;
  var flips = 0;
  var isFlipped = [];
  var flipCount = 0;
  for (var i = 0; i</p>< n; i++) {
    if (i ><p>= k && isFlipped[i - k]) {
      flipCount--;
    }
    if ((nums[i] + flipCount) % 2 === 0) {
      if (i + k > n) return -1;
      flips++;
      flipCount++;
      isFlipped[i] = true;
    }
  }
  return flips;
}</p>

Best Answers

java
class Solution {
    public int solution(int[] nums, int k) {
        int n = nums.length;
        int flips = 0;
        int flipCount = 0;
        boolean[] isFlipped = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (i >= k && isFlipped[i - k]) flipCount--;
            if ((nums[i] + flipCount) % 2 == 0) {
                if (i + k > n) return -1;
                flips++;
                flipCount++;
                isFlipped[i] = true;
            }
        }
        return flips;
    }
}