Course4all
Join us on telegram
Home/dsa/Greedy/Minimum Number of K Consecutive Bit Flips

Minimum Number of K Consecutive Bit Flips

Master this topic with zero to advance depth.

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 and reversing all bits. Return the minimum flips to make all elements 1.

Visual Representation

nums = [0, 1, 0], k = 1 i=0: 0 -> Flip! [1, 1, 0], ans=1 i=1: 1 -> OK. i=2: 0 -> Flip! [1, 1, 1], ans=2 Total: 2
Hard

Examples

Input: nums = [0,1,0], k = 1
Output: 2

Flip nums[0], then flip nums[2].

Approach 1

Level I: Brute Force Simulation

Intuition

Traverse the array from left to right. Whenever we encounter a 0, we flip the next k elements. If at any point we need to flip but don't have enough elements left, it's impossible.

Thought Process

  1. For each index i from 0 to n-1:
    • If nums[i] == 0:
      • Check if i + k > n. If so, return -1.
      • Manually flip nums[i...i+k-1].
      • Increment ans.
  2. Return ans.
⏱ O(N * K)💾 O(1) (modifying input) or O(N) (copy).

Detailed Dry Run

nums = [0, 1, 0, 1], k = 2

  1. i=0: nums[0]=0. Flip [0,1]. nums becomes [1, 0, 0, 1]. ans=1.
  2. i=1: nums[1]=0. Flip [1,2]. nums becomes [1, 1, 1, 1]. ans=2.
  3. i=2,3: nums[i]=1. OK. Result: 2
java
public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (i + k > n) return -1;
                for (int j = i; j < i + k; j++) nums[j] ^= 1;
                ans++;
            }
        }
        return ans;
    }
}
Approach 2

Level II: Greedy with Queue

Intuition

Instead of manually flipping elements, use a queue to track which indices still have an active flip effect. This avoids the O(K)O(K) inner loop.

Thought Process

  1. Maintain a queue of indices where a flip was initiated.
  2. At each index i, remove expired flips from the queue (indices jj where j+k≤ij + k \le i).
  3. The number of flips currently affecting i is queue.size().
  4. If nums[i] is effectively 0 (i.e., nums[i] == queue.size() % 2), start a new flip at i.
⏱ O(N)💾 O(K) for the queue.

Detailed Dry Run

nums = [0, 0, 0], k = 2 i=0: nums[0]=0, q=[] (size 0). 0==0. Push 0. q=[0], ans=1. i=1: nums[1]=0, q=[0] (size 1). 0!=1. OK. i=2: i-k=0. Expire 0. q=[]. nums[2]=0. 0==0. Push 2. i+k > n. Return -1.

java
public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        Queue<Integer> q = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!q.isEmpty() && q.peek() + k <= i) q.poll();
            if (nums[i] == q.size() % 2) {
                if (i + k > nums.length) return -1;
                q.add(i);
                ans++;
            }
        }
        return ans;
    }
}
Approach 3

Level III: Optimal Greedy (Sliding Window Flips)

Intuition

Traverse left to right. If nums[i] is 0 after all previous flips affecting it, we MUST flip the window starting at i. Use a queue or difference array to track active flips efficiently.

Thought Process

  1. curFlips = count of active flips affecting index i.
  2. When index i reaches k, remove the effect of the flip that started at i-k.
  3. If nums[i] is effectively 0 (i.e., nums[i] == curFlips % 2), flip it.

Pattern: Greedy Sliding Window Flip

⏱ O(N).💾 O(N) for flip tracking (can be O(1) if modifying input).

Detailed Dry Run

nums = [0,0,0,1,0], k=3 i=0: nums[0]=0, cur=0. Flip! ans=1, cur=1, mark[0]=1 i=1,2: cur=1, nums[i] effectively 1. OK. i=3: i>=3, remove mark[0]. cur=0. nums[3]=1. OK. i=4: nums[4]=0, cur=0. Flip! i+k > n. FAIL.

java
public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, curFlips = 0, ans = 0;
        int[] isFlipped = new int[n];
        for (int i = 0; i < n; i++) {
            if (i >= k) curFlips ^= isFlipped[i - k];
            if (nums[i] == curFlips) {
                if (i + k > n) return -1;
                isFlipped[i] = 1;
                curFlips ^= 1;
                ans++;
            }
        }
        return ans;
    }
}
← Previous QuestionReorganize String
Next Question →Weighted Job Scheduling