Minimum Number of K Consecutive Bit Flips solution and explanation
Google
9 more videos on this problem
Minimum Number of K Consecutive Bit Flips | 3 Approaches | Leetcode 995 | 3191 | codestorywithMIKcodestorywithMIK · 1:03:24 · 19K views
Minimum Number of K Consecutive Bit Flips - Leetcode 995 - PythonNeetCodeIO · 17:30 · 18K views
995, 3191, 3192 Minimum Number of K Consecutive Bit Flips | Bit Manipulation | Sliding Wind | GreedyAryan Mittal · 35:03 · 13K views
LeetCode 995. Minimum Number of K Consecutive Bit FlipsHappy Coding · 26:44 · 7K views
995. Minimum Number of K Consecutive Bit Flips (Leetcode Hard)Programming Live with Larry · 8:24 · 3K views
995. Minimum Number of K Consecutive Bit Flips | Leetcode Daily 24/06/24 | Hard | Prefix sum | O(N)AlgorithmHQ · 25:48 · 1K views
Daily Leetcode #1546: Jun 24, 2024 - 995. Minimum Number of K Consecutive Bit FlipsProgramming Live with Larry · 14:16 · 1K views
Minimum Number of K Consecutive Bit Flips (LeetCode 995) (Hard) (Sliding Window and Queue)CodeWithARB · 54:48 · 785 views
Minimum Number of K Consecutive Bit Flips - Leetcode 995 - Explanation & Dry RunArindam Keswani · 26:00 · 179 views
LeetCode 995 - Minimum Number of Consecutive Bit Flips - JavaAlpha-Code · 15:23 · 165 views
The 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 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.length
Approach overview
Problem Overview: You are given a binary array nums and an integer k. In one operation you can choose any subarray of length k and flip every bit (0 → 1, 1 → 0). The task is to compute the minimum number of such flips required so the entire array becomes all 1s, or return -1 if it is impossible.
Approach 1: Greedy with Queue (O(n) time, O(k) space)
This method processes the array from left to right and greedily decides whether to start a flip at each index. If the current effective bit is 0, a flip must start here; delaying it would leave that position permanently incorrect. A queue tracks the indices where flips begin so you know when a flip window expires. The parity of active flips determines whether the current bit is effectively flipped. Each step performs constant work: check queue front, update flip parity, and optionally enqueue a new flip. This approach is intuitive and explicitly models the sliding window of active flips using a queue from the queue family of techniques.
Approach 2: Sliding Window In-Place (O(n) time, O(1) extra space)
This optimized greedy technique avoids an explicit queue. Instead, the array itself stores markers indicating where flips start. As you iterate, maintain a variable representing how many flips are currently affecting the position (tracked via parity). When a flip starts, mark the index and toggle the active flip state. When the window moves past k positions, remove the effect of the flip that started there. The logic behaves like a sliding window where each position is influenced by flips started in the previous k indices. The key idea is that only the parity of flips matters, so you never need to actually modify every bit.
The in-place variant is effectively a greedy window combined with prefix-style tracking of flip effects, similar to ideas used in prefix sum difference arrays. It avoids extra data structures while still ensuring each element is processed exactly once.
Recommended for interviews: The greedy sliding-window strategy with O(n) time is the expected solution. Starting with the queue-based version clearly communicates the logic of active flips. Transitioning to the in-place optimization demonstrates deeper understanding of window effects and space optimization. Interviewers typically look for the greedy insight: if the current bit evaluates to 0, you must flip starting there immediately.
Approach 1: Greedy Approach with Queue
This approach uses a greedy strategy with the help of a queue to track the index of flips. The idea is to traverse through the array and only flip when necessary, using a queue to efficiently track start points of flips that affect the current position. When flipping, add the index to a queue. Dequeue any index that is outside the current consideration (i.e., more than 'k' steps away).
from collections import deque
def minKBitFlips(nums, k):
flip = deque()
flips = 0
flip_count = 0
for i in range(len(nums)):
if flip and flip[0] + k <= i:
flip.popleft()
flip_count -= 1
if nums[i] == flip_count % 2:
if i + k > len(nums):
return -1
flips += 1
flip.append(i)
flip_count += 1
return flips
print(minKBitFlips([0, 0, 0, 1, 0, 1, 1, 0], 3)) # Output: 3import java.util.*;
class Solution {
public int minKBitFlips(int[] nums, int k) {
Queue<Integer> flip = new LinkedList<>();
int flips = 0, flip_count = 0;
for (int i = 0; i < nums.length; i++) {
if (!flip.isEmpty() && flip.peek() + k <= i) {
flip.poll();
flip_count--;
}
if (nums[i] == flip_count % 2) {
if (i + k > nums.length) return -1;
flips++;
flip.add(i);
flip_count++;
}
}
return flips;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {0, 0, 0, 1, 0, 1, 1, 0};
int k = 3;
System.out.println(sol.minKBitFlips(nums, k)); // Output: 3
}
}#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int minKBitFlips(vector<int>& nums, int k) {
int flips = 0, flip_count = 0;
vector<int> flip(nums.size(), 0);
for (int i = 0; i < nums.size(); i++) {
if (i >= k) flip_count ^= flip[i - k];
if (nums[i] == flip_count % 2) {
if (i + k > nums.size()) return -1;
flips++;
flip_count ^= 1;
flip[i] = 1;
}
}
return flips;
}
int main() {
vector<int> nums = {0, 0, 0, 1, 0, 1, 1, 0};
int k = 3;
cout << minKBitFlips(nums, k) << endl; // Output: 3
return 0;
}function minKBitFlips(nums, k) {
let flips = 0;
let flipCount = 0;
let queue = [];
for (let i = 0; i < nums.length; i++) {
if (queue.length && queue[0] + k <= i) {
queue.shift();
flipCount--;
}
if (nums[i] === flipCount % 2) {
if (i + k > nums.length) return -1;
flips++;
queue.push(i);
flipCount++;
}
}
return flips;
}
console.log(minKBitFlips([0, 0, 0, 1, 0, 1, 1, 0], 3)); // Output: 3#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int minKBitFlips(int* nums, int numsSize, int k) {
int flips = 0;
int flip_count = 0;
int* flip = (int*)calloc(numsSize, sizeof(int));
for (int i = 0; i < numsSize; ++i) {
if (i >= k) flip_count ^= flip[i - k];
if (nums[i] == flip_count % 2) {
if (i + k > numsSize) return -1;
flips++;
flip_count ^= 1;
flip[i] = 1;
}
}
free(flip);
return flips;
}
int main() {
int nums[] = {0, 0, 0, 1, 0, 1, 1, 0};
int k = 3;
printf("%d\n", minKBitFlips(nums, 8, k)); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinKBitFlips(int[] nums, int k) {
Queue<int> flip = new Queue<int>();
int flips = 0, flip_count = 0;
for (int i = 0; i < nums.Length; i++) {
if (flip.Count > 0 && flip.Peek() + k <= i) {
flip.Dequeue();
flip_count--;
}
if (nums[i] == flip_count % 2) {
if (i + k > nums.Length) return -1;
flips++;
flip.Enqueue(i);
flip_count++;
}
}
return flips;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {0, 0, 0, 1, 0, 1, 1, 0};
int k = 3;
Console.WriteLine(sol.MinKBitFlips(nums, k)); // Output: 3
}
}Uses a deque to handle the effect of previous flips, checking current bit flip status via XOR. The approach handles flips by performing operations on bit positions with necessary adjustment for past operations using a queue-like structure.
The time complexity is O(n), as it processes each element once, and the space complexity is O(n) due to the deque used for flip management.
Approach 2: Sliding Window In-Place Approach
This approach utilizes a sliding window technique with a flipping effect flag, which acts as a state tracker for ongoing flip operations. Using an in-place element flipping marker in the array enables this technique to minimize memory usage and avoid using additional data structures to track state.
def minKBitFlips(A, K):
flips = 0
flip_parity = 0
for i in range(len(A)):
if i >= K and A[i - K] > 1:
flip_parity ^= 1
A[i - K] -= 2
if A[i] == flip_parity:
if i + K > len(A):
return -1
flips += 1
flip_parity ^= 1
A[i] += 2
return flips
print(minKBitFlips([0, 0, 0, 1, 0, 1, 1, 0], 3)) # Output: 3import java.util.*;
class Solution {
public int minKBitFlips(int[] A, int K) {
int flips = 0;
for (int i = 0, flip = 0; i < A.length; ++i) {
if (i >= K && A[i - K] > 1) {
A[i - K] -= 2;
flip ^= 1;
}
if (A[i] == flip) {
if (i + K > A.length) return -1;
++flips;
flip ^= 1;
A[i] += 2;
}
}
return flips;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {0, 0, 0, 1, 0, 1, 1, 0};
int k = 3;
System.out.println(sol.minKBitFlips(nums, k)); // Output: 3
}
}#include <vector>
#include <iostream>
using namespace std;
int minKBitFlips(vector<int>& A, int K) {
int flips = 0, flipparity = 0;
for (int i = 0; i < A.size(); i++) {
if (i >= K && A[i - K] > 1) {
A[i - K] -= 2;
flipparity ^= 1;
}
if (A[i] == flipparity) {
if (i + K > A.size()) return -1;
flips++;
flipparity ^= 1;
A[i] += 2;
}
}
return flips;
}
int main() {
vector<int> A = {0, 0, 0, 1, 0, 1, 1, 0};
int K = 3;
cout << minKBitFlips(A, K) << endl; // Output: 3
return 0;
}function minKBitFlips(A, K) {
let flips = 0, flipCount = 0;
for (let i = 0; i < A.length; ++i) {
if (i >= K && A[i - K] > 1) {
A[i - K] -= 2;
flipCount ^= 1;
}
if (A[i] == flipCount) {
if (i + K > A.length) return -1;
flips++;
flipCount ^= 1;
A[i] += 2;
}
}
return flips;
}
console.log(minKBitFlips([0, 0, 0, 1, 0, 1, 1, 0], 3)); // Output: 3#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int minKBitFlips(int* A, int ASize, int K) {
int i = 0, flips = 0;
for (i = 0; i <= ASize; i++) {
if (i < ASize && i >= K && A[i - K] > 1) {
A[i - K] -= 2;
flips--;
}
if (i < ASize && ((A[i] & 1) == flips % 2)) {
if (i + K > ASize) return -1;
flips++;
A[i] += 2;
}
}
return flips;
}
int main() {
int nums[] = {0, 0, 0, 1, 0, 1, 1, 0};
int K = 3;
printf("%d\n", minKBitFlips(nums, 8, K)); // Output: 3
return 0;
}using System;
public class Solution {
public int MinKBitFlips(int[] A, int K) {
int flips = 0;
for (int i = 0, flip = 0; i < A.Length; ++i) {
if (i >= K && A[i - K] > 1) {
A[i - K] -= 2;
flip ^= 1;
}
if (A[i] == flip) {
if (i + K > A.Length) return -1;
++flips;
flip ^= 1;
A[i] += 2;
}
}
return flips;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {0, 0, 0, 1, 0, 1, 1, 0};
int k = 3;
Console.WriteLine(sol.MinKBitFlips(nums, k)); // Output: 3
}
}Leverages an `A[i] += 2` transformation as a flip tracker, effectively acting as a built-in state flag for toggles. This enacts flipping logic control using low-memory alteration.
Time is O(n), linear through the array, achieving O(1) space by focusing on direct input manipulation without additional resource-heavy state variables.
Approach 3: Difference Array
We notice that the result of reversing several consecutive elements is independent of the order of the reversals. Therefore, we can greedily consider the number of reversals needed at each position.
We can process the array from left to right.
Suppose we need to process position i, and the elements to the left of position i have been processed. If the element at position i is 0, then we must perform a reversal operation, we need to reverse the elements in the interval [i,..i+k-1]. Here we use a difference array d to maintain the number of reversals at each position, then to determine whether the current position i needs to be reversed, we only need to see s = sum_{j=0}^{i}d[j] and the parity of nums[i]. If s and nums[i] have the same parity, then the element at position i is still 0 and needs to be reversed. At this time, we check whether i+k exceeds the length of the array. If it exceeds the length of the array, then the target cannot be achieved, return -1. Otherwise, we increase d[i] by 1, decrease d[i+k] by 1, increase the answer by 1, and increase s by 1.
In this way, when we have processed all the elements in the array, we can return the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
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]) {
if (i + k > n) {
return -1;
}
d[i]++;
d[i + k]--;
s++;
ans++;
}
}
return ans;
}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
}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
}
}Approach 4: Sliding Window
We can use a variable flipped to indicate whether the current position has been flipped. If flipped = 1, it means the current position has already been flipped; otherwise, it means the current position has not been flipped. For positions that have been flipped, we can set their value to -1, allowing us to distinguish which positions have been flipped.
Next, we traverse the array from left to right. For each position i, if i geq k and the element at position i-k is -1, then the flip state of the current position should be the opposite of the flip state of the previous position. That is, flipped = flipped \oplus 1. If the element at the current position is the same as the current flip state, then we need to flip the current position. At this point, we check if i+k exceeds the length of the array. If it does, then it is impossible to achieve the goal, and we return -1. Otherwise, we invert the current flip state, increase the answer by 1, and set the element at the current position to -1.
By processing all elements in the array in this manner, we can return the answer upon completion.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
function minKBitFlips(nums: number[], k: number): number {
const n = nums.length;
let [ans, flipped] = [0, 0];
for (let i = 0; i < n; i++) {
if (nums[i - k] === -1) {
flipped ^= 1;
}
if (nums[i] === flipped) {
if (i + k > n) {
return -1;
}
flipped ^= 1;
++ans;
nums[i] = -1;
}
}
return ans;
}func minKBitFlips(nums []int, k int) (ans int) {
flipped := 0
for i, x := range nums {
if i >= k && nums[i-k] == -1 {
flipped ^= 1
}
if flipped == x {
if i+k > len(nums) {
return -1
}
flipped ^= 1
ans++
nums[i] = -1
}
}
return
}impl Solution {
pub fn min_k_bit_flips(mut nums: Vec<i32>, k: i32) -> i32 {
let mut ans = 0;
let mut flipped = 0;
let k = k as usize;
for i in 0..nums.len() {
if i >= k && nums[i - k] == -1 {
flipped ^= 1;
}
if flipped == nums[i] {
if i + k > nums.len() {
return -1;
}
flipped ^= 1;
ans += 1;
nums[i] = -1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Queue | The time complexity is O(n), as it processes each element once, and the space complexity is O(n) due to the deque used for flip management. |
| Sliding Window In-Place Approach | Time is O(n), linear through the array, achieving O(1) space by focusing on direct input manipulation without additional resource-heavy state variables. |
| Difference Array | – |
| Sliding Window | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Flipping | O(n*k) | O(1) | Conceptual baseline; useful to understand the flipping mechanics but too slow for large inputs. |
| Greedy with Queue | O(n) | O(k) | Clear implementation that explicitly tracks active flip windows using a queue. |
| Sliding Window In-Place | O(n) | O(1) | Optimal approach when memory usage matters; avoids extra structures while maintaining flip parity. |
Frequently asked questions
Is Minimum Number of K Consecutive Bit Flips easy or hard?
LeetCode classifies this problem as Hard because the greedy insight is not immediately obvious. The challenge lies in efficiently tracking overlapping flip operations and avoiding repeated O(k) updates for every flip.
Minimum Number of K Consecutive Bit Flips Python/Java solution
Both Python and Java implementations typically follow the greedy sliding window pattern. Python solutions often use collections.deque for tracking flips, while Java implementations use ArrayDeque or simulate the window with integer markers. Both achieve O(n) time complexity.
How to solve Minimum Number of K Consecutive Bit Flips in O(n)?
Traverse the array while tracking how many flips are currently affecting the position. If the effective bit is 0, start a new flip window of length k. Maintain active flip parity using either a queue of start indices or an in-place marker technique so expired flips are removed as the window moves.
What is the best approach for Minimum Number of K Consecutive Bit Flips?
The best approach is a greedy sliding window algorithm that processes the array left to right. When the current effective bit becomes 0, a flip must start at that position. Tracking active flips using a queue or in-place markers ensures each element is processed once, resulting in O(n) time complexity.
Is Minimum Number of K Consecutive Bit Flips asked at Google/Amazon/Meta?
Variations of this problem appear in interviews at large tech companies including Google, Amazon, and Meta because it tests greedy reasoning, sliding window control, and efficient state tracking. Candidates must recognize that flips should be applied immediately when a 0 is encountered.
What data structure is used in Minimum Number of K Consecutive Bit Flips?
Common implementations use a queue or deque to track the starting indices of active flips. Some optimized solutions avoid extra structures by storing flip markers directly in the array and maintaining a running parity variable to simulate the sliding window.
What is the time complexity of Minimum Number of K Consecutive Bit Flips?
The optimal solutions run in O(n) time because each index is visited once while maintaining the effect of previous flips. Queue operations or window updates are constant time. Space complexity is O(k) for the queue version and O(1) for the in-place sliding window optimization.