🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve the problem of flipping k-bit subarrays in a binary array nums
so that there are no 0
s left, we need to determine the minimum number of flips required. If it's not possible to achieve this, we return -1
.
The key intuition is to track the flip operations using a sliding window technique. By keeping track of the current state of flips, we can efficiently decide whether to flip the subarray starting at the current index or not.
Approach
- Initialize Variables:
-
flag
to keep track of the cumulative flip state. -res
to count the number of flips performed. -n
to store the length of the input arraynums
. - Iterate Through the Array:
- For each element
nums[i]
: - Calculate the current statecur
by XORingnums[i]
withflag
. - Ifcur
is0
, it means the current bit is0
and needs to be flipped. - If flipping a subarray starting ati
would exceed the bounds of the array (i + k > n
), return-1
. - Otherwise, increment the flip counterres
and toggle theflag
to indicate a new flip operation. - After potentially flipping, setnums[i]
to the flipped value (1 - cur
). - Adjust Flip State:
- After processing the current element, update the
flag
based on the element that falls out of the flip window (i.e.,i + 1 - k
). - Return the Result:
- Return the total number of flips
res
.
Complexity
- Time Complexity:
O(n)
, wheren
is the length of the arraynums
. We iterate through the array once, and each operation inside the loop isO(1)
. - Space Complexity:
O(1)
, since we use a constant amount of extra space regardless of the input size.
Code Explanation
Function Signature
var minKBitFlips = function (nums, k) {
- nums: An array of binary digits (0s and 1s).
- k: The length of the subarray to flip.
Variables
var flag = 0;
var res = 0;
var n = nums.length;
- flag: Keeps track of whether the current bit has been flipped an odd or even number of times.
- res: Counts the number of flips performed.
- n: The length of the input array
nums
.
Main Loop
for (var i = 0; i < n; i++) {
The loop iterates through each element of the array nums
.
Determine Current Bit State
var cur = nums[i] ^ flag;
cur
represents the current state of the bit after accounting for the flips indicated byflag
.- XOR (
^
) operation is used to determine the current state: ifflag
is 1, it means the bit has been flipped an odd number of times, otherwise even.
Check If Flip is Needed
if (cur === 0) {
if (i + k > n) return -1;
flag ^= 1;
res++;
}
- If
cur
is 0 (meaning the current bit is 0 and needs to be flipped): - Check if there are enough bits remaining to perform a k-bit flip (i + k > n
). If not, return -1 (not possible to flip). - Toggle theflag
to indicate a flip. - Increment the flip countres
.
Mark the Flip
nums[i] = 1 - cur;
- Change the current bit to 1 to mark that this position has been considered for a flip.
Maintain Flip State
if (i + 1 - k >= 0) flag ^= nums[i + 1 - k];
- Once a window of
k
bits has passed, adjust theflag
back by XORing it with the bit that isk
positions behind the current position to maintain the correct flip state for the rest of the array.
Return Result
return res;
- Finally, return the total number of flips performed.
This function efficiently determines the minimum number of k-bit flips required to ensure there are no 0s in the array nums
, or returns -1 if it's not possible.
Code
C++
class Solution {
public:
int minKBitFlips(vector& nums, int k) {
int flag = 0;
int res = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
int cur = nums[i] ^ flag;
if (cur == 0) {
if (i + k > n) return -1;
flag ^= 1;
res++;
}
nums[i] = 1 - cur;
if (i + 1 - k >= 0) flag ^= nums[i + 1 - k];
}
return res;
}
};
Python
class Solution:
def minKBitFlips(self, nums: List[int], k: int) -> int:
flag = 0
res = 0
n = len(nums)
for i in range(n):
cur = nums[i] ^ flag
if cur == 0:
if i + k > n:
return -1
flag ^= 1
res += 1
nums[i] = 1 - cur
if i + 1 - k >= 0:
flag ^= nums[i + 1 - k]
return res
Java
class Solution {
public int minKBitFlips(int[] nums, int k) {
int flag = 0;
int res = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
int cur = nums[i] ^ flag;
if (cur == 0) {
if (i + k > n) return -1;
flag ^= 1;
res++;
}
nums[i] = 1 - cur;
if (i + 1 - k >= 0) flag ^= nums[i + 1 - k];
}
return res;
}
}
JavaScript
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minKBitFlips = function (nums, k) {
var flag = 0;
var res = 0;
var n = nums.length;
for (var i = 0; i < n; i++) {
var cur = nums[i] ^ flag;
if (cur === 0) {
if (i + k > n) return -1;
flag ^= 1;
res++;
}
nums[i] = 1 - cur;
if (i + 1 - k >= 0) flag ^= nums[i + 1 - k];
}
return res;
};