Minimum Number of K Consecutive Bit Flips — Solution
Minimum Number of K Consecutive Bit Flips solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Number of K Consecutive Bit Flips is a hard coding problem on arrays, greedy and bit manipulation, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Arrays, Greedy, Bit Manipulation, Prefix Sum, Sliding Window
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
One k-bit flip picks a subarray of exactly k consecutive elements of the binary array nums and flips every bit in it.
Return the minimum number of k-bit flips needed to make every element 1, or -1 if it is impossible.
Example 1
Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip index 0, then index 2.
Example 2
Input: nums = [1,1,0], k = 2
Output: -1
Explanation: Any flip covering the 0 would also break a 1.
Example 3
Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3
Constraints
1 <= nums.length <= 1000001 <= k <= nums.lengthnums[i] is 0 or 1
Hints for Minimum Number of K Consecutive Bit Flips
Hint 1
Scan left to right: the leftmost
0can only be fixed by the flip that starts at it.Hint 2
That makes the greedy forced — no choice is ever available.
Hint 3
Track how many flips still cover the current index with a difference array, so you know its effective value in constant time.
How to solve Minimum Number of K Consecutive Bit Flips
The decision at each index is forced: if the element is currently 0, the only flip that can fix it without disturbing anything to its left is the one starting exactly there. Track the parity of active flips with a difference array so the effective value is known in constant time.
Approach
- Keep
cur, the number of flips currently covering indexi, updated by a difference arraydiff. - The effective value at
iis(nums[i] + cur) % 2. - If it is
0, start a flip ati: increment the answer andcur, and schedulediff[i + k]--so the flip expires. - If a flip would run past the end (
i + k > n), the task is impossible.
Why it works
Flips are commutative and each position's final value depends only on the parity of flips covering it, so processing left to right loses nothing. At index i, every flip starting before i has already been decided, and a flip starting after i cannot cover i — so the flip at i is the only remaining lever, making the greedy choice forced and therefore optimal.
Complexity
- Time —
O(n) - Space —
O(n), or O(1) with a queue of expiry positions
Pitfalls
- Actually flipping the
kelements each time isO(n · k)and times out. - Forgetting to expire a flip at
i + kleavescurpermanently wrong. - The impossibility check must happen before scheduling, or the difference array is indexed out of range.
Reference solution
Python
from typing import List
def minKBitFlips(nums: List[int], k: int) -> int:
n = len(nums)
diff = [0] * (n + 1)
flips = 0
cur = 0
for i in range(n):
cur += diff[i]
if (nums[i] + cur) % 2 == 0:
if i + k > n:
return -1
flips += 1
cur += 1
diff[i + k] -= 1
return flipsJava
public static int minKBitFlips(int[] nums, int k) {
int n = nums.length;
int[] diff = new int[n + 1];
int flips = 0, cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
if ((nums[i] + cur) % 2 == 0) {
if (i + k > n) return -1;
flips++;
cur++;
diff[i + k]--;
}
}
return flips;
}C++
int minKBitFlips(vector<int>& nums, int k) {
int n = (int) nums.size();
vector<int> diff(n + 1, 0);
int flips = 0, cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
if ((nums[i] + cur) % 2 == 0) {
if (i + k > n) return -1;
flips++;
cur++;
diff[i + k]--;
}
}
return flips;
}JavaScript
var minKBitFlips = function(nums, k) {
var n = nums.length;
var diff = [];
for (var t = 0; t <= n; t++) diff.push(0);
var flips = 0, cur = 0;
for (var i = 0; i < n; i++) {
cur += diff[i];
if ((nums[i] + cur) % 2 === 0) {
if (i + k > n) return -1;
flips++;
cur++;
diff[i + k]--;
}
}
return flips;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms