Dare2Solve
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.
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 array nums
.Iterate Through the Array:
nums[i]
:
cur
by XORing nums[i]
with flag
.cur
is 0
, it means the current bit is 0
and needs to be flipped.
i
would exceed the bounds of the array (i + k > n
), return -1
.res
and toggle the flag
to indicate a new flip operation.nums[i]
to the flipped value (1 - cur
).Adjust Flip State:
flag
based on the element that falls out of the flip window (i.e., i + 1 - k
).Return the Result:
res
.O(n)
, where n
is the length of the array nums
. We iterate through the array once, and each operation inside the loop is O(1)
.O(1)
, since we use a constant amount of extra space regardless of the input size.var minKBitFlips = function (nums, k) {
var flag = 0;
var res = 0;
var n = nums.length;
nums
.for (var i = 0; i < n; i++) {
The loop iterates through each element of the array nums
.
var cur = nums[i] ^ flag;
cur
represents the current state of the bit after accounting for the flips indicated by flag
.^
) operation is used to determine the current state: if flag
is 1, it means the bit has been flipped an odd number of times, otherwise even.if (cur === 0) {
if (i + k > n) return -1;
flag ^= 1;
res++;
}
cur
is 0 (meaning the current bit is 0 and needs to be flipped):
i + k > n
). If not, return -1 (not possible to flip).flag
to indicate a flip.res
.nums[i] = 1 - cur;
if (i + 1 - k >= 0) flag ^= nums[i + 1 - k];
k
bits has passed, adjust the flag
back by XORing it with the bit that is k
positions behind the current position to maintain the correct flip state for the rest of the array.return res;
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.
class Solution {
public:
int minKBitFlips(vector<int>& 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;
}
};
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
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;
}
}
/**
* @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;
};