
Description
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.
Intuition
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.
Approach
- Initialize two pointers,
l
andr
, representing the left and right bounds of the sliding window. - Traverse through the array with the right pointer
r
, adding each element to the current window. - Decrease
k
when a 0 is encountered in the window. - If
k
becomes negative (indicating more thank
0s in the window), increment the left pointerl
to reduce the size of the window and restorek
to a non-negative value. - Track the maximum length of the window throughout the process.
- Return the maximum length found.
Complexity
Time Complexity:
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.
Space Complexity:
O(1)
, as the algorithm only uses a few extra variables to keep track of the pointers and counts.
Code
C++
class Solution {
public:
int longestOnes(std::vector& 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;
}
};
Python
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
Java
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;
}
}
JavaScript
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
};