Max Consecutive Ones [Medium] — K-Flip Sliding Window
Sanjeev SharmaAdvertisement
Problem Statement
Given a binary array and integer k (number of allowed flips), return the maximum consecutive 1s achievable.
Input: nums=[1,1,1,0,0,0,1,1,1,1,0], k=2 → Output: 6
Intuition
Same as Max Consecutive Ones III — variable sliding window counting zeros. When zero count > k, shrink left.
Solutions
Python
def findMaxConsecutiveOnes(nums: list[int], k: int) -> int:
left = zeros = ans = 0
for right, val in enumerate(nums):
if val == 0: zeros += 1
while zeros > k:
if nums[left] == 0: zeros -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
C++
int findMaxConsecutiveOnes(vector<int>& nums, int k) {
int left=0, zeros=0, ans=0;
for(int r=0;r<nums.size();r++){
if(!nums[r]) zeros++;
while(zeros>k){if(!nums[left++])zeros--;}
ans=max(ans,r-left+1);
}
return ans;
}
Complexity
- Time: O(n), Space: O(1)
Advertisement
