Minimum Number of K Consecutive Bit Flips
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most efficient approach, achieving linear time complexity with constant extra space. It cleverly uses the input array itself to store information about ongoing flips, eliminating the need for an auxiliary data structure like a queue.
Algorithm
- Initialize
flips = 0andcurrent_flip_effect = 0. - Iterate
ifrom0tonums.length - 1. - If
i >= kandnums[i-k] > 1, it means a flip started ati-k. Its effect is now over, so we togglecurrent_flip_effect. - The current effective bit is
(nums[i] + current_flip_effect) % 2. - If this effective bit is
0:- If
i + k > nums.length, return-1. - Increment
flips. - Toggle
current_flip_effect. - Mark
nums[i]by adding 2 to it, to signal that a flip started here.
- If
Walkthrough
The logic is similar to the sliding window approach, but instead of a queue, we use a single variable, current_flip_effect, to track the parity (even or odd) of active flips. We iterate from i = 0 to n-1. At each step i, we need to know if current_flip_effect should change. A change occurs if a flip window that started k positions ago is now ending. To signal this, when we decide to flip at an index j, we modify nums[j] to a value other than 0 or 1 (e.g., by adding 2). This acts as a marker. When we reach index i, we first check nums[i-k] (if i >= k). If it's marked, we know a flip started at i-k and its effect ends here, so we update current_flip_effect. Then, we determine the effective value of nums[i] using its original value and current_flip_effect. If a flip is needed, we update current_flip_effect, increment the total flip count, and mark nums[i] to signal the start of a new flip.
class Solution { public int minKBitFlips(int[] nums, int k) { int n = nums.length; int flips = 0; int currentFlipEffect = 0; // 0 for even flips, 1 for odd flips for (int i = 0; i < n; i++) { // A flip started at i-k is no longer active if (i >= k && nums[i - k] > 1) { currentFlipEffect ^= 1; } // Check if the current bit needs to be flipped // (nums[i] + currentFlipEffect) % 2 == 0 is equivalent to nums[i] == currentFlipEffect if (nums[i] == currentFlipEffect) { // If we need to flip but can't, it's impossible if (i + k > n) { return -1; } // Perform a flip flips++; currentFlipEffect ^= 1; // Mark that a flip started at this index nums[i] += 2; } } return flips; }}Complexity
Time
O(N). A single pass through the array is performed.
Space
O(1). We only use a few variables for tracking state and modify the input array in-place.
Trade-offs
Pros
Most efficient solution in both time and space.
Achieves the optimal O(1) space complexity.
Cons
The logic is more subtle due to the in-place modification of the array to store state.
Modifies the input array, which might not be permissible in all contexts.
This approach directly simulates the greedy strategy. We iterate through the array, and whenever we encounter a 0, we perform a k-bit flip on the subarray starting at that position.
Algorithm
- Initialize
flips = 0. - Iterate
ifrom0tonums.length - k. - If
nums[i]is0:- Increment
flips. - Iterate
jfromitoi + k - 1. - Flip
nums[j](e.g.,nums[j] = 1 - nums[j]).
- Increment
- Iterate
ifromnums.length - k + 1tonums.length - 1. - If
nums[i]is0, return-1. - Return
flips.
Walkthrough
The core idea is that to make the array all 1s, we must process it from left to right. If nums[i] is 0, the only way to change it to 1 is by performing a flip on the subarray nums[i...i+k-1]. Any flip starting at an index greater than i will not affect nums[i]. Therefore, we have no choice but to flip at i. This greedy choice is optimal.
The algorithm iterates from i = 0 to n-k. If nums[i] is 0, it increments a flip counter and then explicitly flips all k bits in the subarray nums[i...i+k-1]. After this loop, it checks the last k-1 elements. If any of them are 0, it's impossible to make them 1 because any flip would extend beyond the array's bounds. In this case, we return -1. Otherwise, the accumulated count is the minimum number of flips.
class Solution { public int minKBitFlips(int[] nums, int k) { int n = nums.length; int flips = 0; for (int i = 0; i <= n - k; i++) { if (nums[i] == 0) { flips++; for (int j = 0; j < k; j++) { nums[i + j] = 1 - nums[i + j]; } } } // Check if the remaining part of the array is all 1s for (int i = n - k + 1; i < n; i++) { if (nums[i] == 0) { return -1; } } return flips; }}Complexity
Time
O(N * K). The outer loop runs up to `N` times, and for each time we decide to flip, the inner loop runs `K` times. In the worst case, this is O(N*K).
Space
O(1), as we modify the input array in-place and use only a few extra variables.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large
NandK, likely to result in a 'Time Limit Exceeded' error on most platforms.
This approach optimizes the simulation by avoiding the O(K) work for each flip. Instead of actually flipping the subarray, we keep track of the "flip effect" on the current element using a sliding window.
Algorithm
- Initialize
flips = 0. - Initialize a queue
flipQueueto store indices where flips start. - Iterate
ifrom0tonums.length - 1. - While
flipQueueis not empty andflipQueue.peek() <= i - k, remove the front element. - The number of active flips is
flipQueue.size(). - The effective value of
nums[i]is(nums[i] + flipQueue.size()) % 2. - If the effective value is
0:- If
i + k > nums.length, return-1. - Increment
flips. - Add
itoflipQueue.
- If
- Return
flips.
Walkthrough
We still follow the same greedy strategy of iterating from left to right. At any index i, the actual value of the bit is original_nums[i] flipped by all active flip operations. An active flip is one that started at an index j such that i is in the range [j, j+k-1].
We can use a queue to store the starting indices of these active flips. The size of the queue tells us how many times the current element i has been flipped. The algorithm iterates from i = 0 to n-1. At each i, we first remove indices j from the front of the queue if their flip window has ended (i.e., j <= i - k). The current number of active flips is the queue's size. We determine the effective bit value: (nums[i] + queue.size()) % 2. If this effective value is 0, we must perform a flip. We check if i + k <= n. If not, it's impossible, so we return -1. Otherwise, we increment our total flip count and add i to the queue.
import java.util.LinkedList;import java.util.Queue; class Solution { public int minKBitFlips(int[] nums, int k) { int n = nums.length; int flips = 0; Queue<Integer> flipQueue = new LinkedList<>(); for (int i = 0; i < n; i++) { // Remove flips that are no longer active if (!flipQueue.isEmpty() && flipQueue.peek() <= i - k) { flipQueue.poll(); } int currentFlips = flipQueue.size(); // Determine the effective value of nums[i] if ((nums[i] + currentFlips) % 2 == 0) { if (i + k > n) { return -1; } flips++; flipQueue.add(i); } } return flips; }}Complexity
Time
O(N). We iterate through the array once. Each index is added to and removed from the queue at most once, leading to amortized O(1) time for queue operations per element.
Space
O(K). The queue can hold at most `K` indices, representing the flips active in the current window.
Trade-offs
Pros
Efficient time complexity, making it suitable for large inputs.
The logic is a clear improvement over the brute-force method.
Cons
Uses extra space proportional to
K, which can be large.
Solutions
Solution
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 (nums[i] % 2 == s % 2) { if (i + k > n) { return -1; } ++d[i]; --d[i + k]; ++s; ++ans; } } return ans; }}class Solution {public: int minKBitFlips(vector<int> &nums, int k) { int n = nums.size(); int d[n + 1]; memset(d, 0, sizeof(d)); int ans = 0, s = 0; for (int 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; }};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 x % 2 == s % 2: if i + k > n: return - 1 d[i] += 1 d[i + k] -= 1 s += 1 ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.