Max Consecutive Ones III
Medium· variable window
Problem
In a binary array you may flip at most k zeros to ones. Return the length of the longest run of consecutive 1s you can achieve.
Examples
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Flipping the zeros at indices 4 and 5 creates the run from index 4 to 9.
Input: nums = [0,0,1,1], k = 0
Output: 2
Constraints
- • 1 <= nums.length <= 10^5
- • nums[i] is 0 or 1
- • 0 <= k <= nums.length
Hints & approach
Hint 1
Rephrase: find the longest subarray that contains at most k zeros.
Hint 2
Expand the right edge and count zeros inside the window.
Hint 3
When the zero count exceeds k, move the left edge until it is back to k.
Approachtry the hints first
Maintain a window [left, right] and the number of zeros inside it. Advance right one step at a time, incrementing the zero count on a 0. While the zero count exceeds k, move left forward, decrementing the count when a 0 leaves. After each step the window is valid, so record its length. Both edges only move forward.
Time O(n) · Space O(1)