Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 <= 1051 <= k <= nums.lengthProblem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Bit Manipulation · Sliding Window
[0,1,0] 1
[1,1,0] 2
[0,0,0,1,0,1,1,0] 3
bulb-switcher)minimum-time-to-remove-all-cars-containing-illegal-goods)number-of-distinct-binary-strings-after-applying-operations)minimum-operations-to-make-binary-array-elements-equal-to-one-i)smallest-number-with-all-set-bits)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #995: Minimum Number of K Consecutive Bit Flips
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 (s % 2 == nums[i]) {
if (i + k > n) {
return -1;
}
++d[i];
--d[i + k];
++s;
++ans;
}
}
return ans;
}
}
// Accepted solution for LeetCode #995: Minimum Number of K Consecutive Bit Flips
func minKBitFlips(nums []int, k int) (ans int) {
n := len(nums)
d := make([]int, n+1)
s := 0
for i, x := range nums {
s += d[i]
if s%2 == x {
if i+k > n {
return -1
}
d[i]++
d[i+k]--
s++
ans++
}
}
return
}
# Accepted solution for LeetCode #995: Minimum Number of K Consecutive Bit Flips
class Solution:
def minKBitFlips(self, nums: List[int], k: int) -> int:
n = len(nums)
d = [0] * (n + 1)
ans = s = 0
for i, x in enumerate(nums):
s += d[i]
if s % 2 == x:
if i + k > n:
return -1
d[i] += 1
d[i + k] -= 1
s += 1
ans += 1
return ans
// Accepted solution for LeetCode #995: Minimum Number of K Consecutive Bit Flips
impl Solution {
pub fn min_k_bit_flips(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut d = vec![0; n + 1];
let mut ans = 0;
let mut s = 0;
for i in 0..n {
s += d[i];
if s % 2 == nums[i] {
if i + (k as usize) > n {
return -1;
}
d[i] += 1;
d[i + (k as usize)] -= 1;
s += 1;
ans += 1;
}
}
ans
}
}
// Accepted solution for LeetCode #995: Minimum Number of K Consecutive Bit Flips
function minKBitFlips(nums: number[], k: number): number {
const n = nums.length;
const d: number[] = Array(n + 1).fill(0);
let [ans, s] = [0, 0];
for (let i = 0; i < n; ++i) {
s += d[i];
if (s % 2 === nums[i] % 2) {
if (i + k > n) {
return -1;
}
d[i]++;
d[i + k]--;
s++;
ans++;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.