Dare2Solve
The problem involves finding the maximum number of consecutive 1s in a binary array by flipping at most k
0s to 1s. This is a common sliding window problem that deals with managing a subarray of consecutive elements under certain constraints.
The intuition behind the solution is to maintain a sliding window that represents a valid sequence where the number of zeros does not exceed k
. As you expand the window by adding new elements, you check whether the sequence is still valid. If the sequence becomes invalid, the window is contracted from the left to restore validity. Throughout this process, the maximum length of valid sequences is tracked.
l
and r
, representing the left and right bounds of the sliding window.r
, adding each element to the current window.k
when a 0 is encountered in the window.k
becomes negative (indicating more than k
0s in the window), increment the left pointer l
to reduce the size of the window and restore k
to a non-negative value.O(n)
, where n
is the number of elements in the array. Each element is processed at most twice, once by the right pointer and once by the left pointer.
O(1)
, as the algorithm only uses a few extra variables to keep track of the pointers and counts.
class Solution {
public:
int longestOnes(std::vector<int>& nums, int k) {
int l = 0, max_num = 0;
for (int r = 0; r < nums.size(); r++) {
k -= 1 - nums[r];
if (k < 0) {
k += 1 - nums[l];
l++;
} else {
max_num = std::max(max_num, r - l + 1);
}
}
return max_num;
}
};
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
l = 0
max_num = 0
for r in range(len(nums)):
k -= 1 - nums[r]
if k < 0:
k += 1 - nums[l]
l += 1
else:
max_num = max(max_num, r - l + 1)
return max_num
class Solution {
public int longestOnes(int[] nums, int k) {
int l = 0, max_num = 0;
for (int r = 0; r < nums.length; r++) {
k -= 1 - nums[r];
if (k < 0) {
k += 1 - nums[l];
l++;
} else {
max_num = Math.max(max_num, r - l + 1);
}
}
return max_num;
}
}
var longestOnes = function (nums, k) {
let l = max_num = 0
for (let r = 0; r < nums.length; r++) {
k -= 1 - nums[r]
if (k < 0) {
k += 1 - nums[l]
l++
} else {
max_num = Math.max(max_num, r - l + 1)
}
console.log(l, r)
}
return max_num
};