Minimum number of k consecutive bit flips

Array Bit Manipulation Queue Sliding Window Prefix Sum

62.3% acceptance

Feb 25, 2026

2055

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_k_bit_flips(nums: Vec<i32>, k: i32) -> i32 {
    let (n, k) = (nums.len(), k as usize);
    let mut flip_diff = vec![0i32; n + 1];
    let mut flips = 0;
    let mut ans = 0;
    for i in 0..n {
      flips += flip_diff[i];
      if (nums[i] as i32 + flips) % 2 == 0 {
        if i + k > n { return -1; }
        ans += 1;
        flips += 1;
        flip_diff[i + k] -= 1;
      }
    }
    ans
  }
}