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 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.
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).
The code uses an auxiliary array `flip` to mark the positions where flips start. The array `flip` is needed to handle the state of whether a bit was flipped or not due to a previous operation. As we iterate through the binary array, we adjust our current state (taking into account the cumulative effect of flips up to `k` positions back) and determine if a flip is necessary. Flips are counted and active flips older than `k` moves are ignored to maintain efficiency.
The time complexity is O(n), where n is the length of nums, because we make a single pass through the array, and the space complexity is O(n) due to the auxiliary array used to track flips.
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.
This implementation uses a simple numeric transition state directly within the input array, marking flips by incrementing values past a threshold. Operation continuity checks thereby use `A[i]` as an in-place modified tracker, optimizing for process space considerations.
Time complexity is O(n) because only single iteration and local modification are performed, while the space complexity is O(1), assisting state via in-place array manipulation.
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.
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).
| Approach | Complexity |
|---|---|
| Greedy Approach with Queue | The time complexity is O(n), where n is the length of nums, because we make a single pass through the array, and the space complexity is O(n) due to the auxiliary array used to track flips. |
| Sliding Window In-Place Approach | Time complexity is O(n) because only single iteration and local modification are performed, while the space complexity is O(1), assisting state via in-place array manipulation. |
| Difference Array | — |
| Sliding Window | — |
| 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. |
Queue Hard: Sliding Window Maximum | Minimum Number of K Consecutive Bit Flips • Coder Army • 24,266 views views
Watch 9 more video solutions →Practice Minimum Number of K Consecutive Bit Flips with our built-in code editor and test cases.
Practice on FleetCode