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.
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; }}Video 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.