Max Consecutive Ones III
Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.
Constraints:
- 1 <= nums.length <= 10^5
- 0 <= k <= nums.length
Examples:
Input: [1,1,1,0,0,0,1,1,1,1,0]
Output: 6
Explanation: Flip the 1st zero and the 2nd zero, then we get 6 consecutive 1's
Solutions
Sliding Window
Time: O(n)Space: O(1)
We use a sliding window to track the maximum number of consecutive 1's. We maintain two pointers, left and right, to represent the current window. We also keep track of the number of zeros in the current window. If the number of zeros exceeds k, we move the left pointer to the right until the number of zeros is less than or equal to k. We update the maximum length of consecutive 1's at each step.
def longestOnes(nums, k):
left, right, max_len = 0, 0, 0
while right < len(nums):
if nums[right] == 0:
k -= 1
while k < 0:
if nums[left] == 0:
k += 1
left += 1
max_len = max(max_len, right - left + 1)
right += 1
return max_lenFollow-up:
What if we can flip at most k 1's instead of 0's?
