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 ofk-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.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

1
2
3
4
5
6

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

Solution

Method 1 – Greedy with Flip Count (Sliding Window)

Intuition

We want to flip only when we see a 0, and each flip affects k consecutive bits. To avoid flipping the same bit multiple times, use a sliding window to track flips and propagate their effect.

Approach

  1. Iterate through nums. If the current bit is 0 (after considering previous flips), flip starting here.
  2. Use a variable to track the number of flips affecting the current position.
  3. Use an auxiliary array to mark where flips end.
  4. If a flip would go out of bounds, return -1.
  5. Count total flips.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <vector>
using namespace std;
class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0, flipped = 0;
        vector<int> isFlipped(n);
        for (int i = 0; i < n; ++i) {
            if (i >= k) flipped ^= isFlipped[i - k];
            if (nums[i] == flipped) {
                if (i + k > n) return -1;
                ++ans; flipped ^= 1; isFlipped[i] = 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func minKBitFlips(nums []int, k int) int {
    n := len(nums)
    isFlipped := make([]int, n)
    flipped, ans := 0, 0
    for i := 0; i < n; i++ {
        if i >= k { flipped ^= isFlipped[i-k] }
        if nums[i] == flipped {
            if i+k > n { return -1 }
            ans++; flipped ^= 1; isFlipped[i] = 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length, ans = 0, flipped = 0;
        int[] isFlipped = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i >= k) flipped ^= isFlipped[i - k];
            if (nums[i] == flipped) {
                if (i + k > n) return -1;
                ++ans; flipped ^= 1; isFlipped[i] = 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minKBitFlips(nums: IntArray, k: Int): Int {
        val n = nums.size
        val isFlipped = IntArray(n)
        var flipped = 0; var ans = 0
        for (i in 0 until n) {
            if (i >= k) flipped = flipped xor isFlipped[i - k]
            if (nums[i] == flipped) {
                if (i + k > n) return -1
                ans++; flipped = flipped xor 1; isFlipped[i] = 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minKBitFlips(self, nums: list[int], k: int) -> int:
        n = len(nums)
        isFlipped = [0] * n
        flipped = ans = 0
        for i in range(n):
            if i >= k:
                flipped ^= isFlipped[i - k]
            if nums[i] == flipped:
                if i + k > n:
                    return -1
                ans += 1
                flipped ^= 1
                isFlipped[i] = 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn min_k_bit_flips(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut is_flipped = vec![0; n];
        let mut flipped = 0;
        let mut ans = 0;
        for i in 0..n {
            if i as i32 >= k { flipped ^= is_flipped[i - k as usize]; }
            if nums[i] == flipped {
                if i as i32 + k > n as i32 { return -1; }
                ans += 1; flipped ^= 1; is_flipped[i] = 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    minKBitFlips(nums: number[], k: number): number {
        const n = nums.length;
        const isFlipped = Array(n).fill(0);
        let flipped = 0, ans = 0;
        for (let i = 0; i < n; ++i) {
            if (i >= k) flipped ^= isFlipped[i - k];
            if (nums[i] === flipped) {
                if (i + k > n) return -1;
                ans++; flipped ^= 1; isFlipped[i] = 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of nums.
  • 🧺 Space complexity: O(n) — for flip tracking array.