Max Consecutive Ones III
Max Consecutive Ones III: given a binary array and an integer k, return the length of the longest subarray of 1s after flipping at most k zeros.
- 1 <= nums.length <= 10⁵
- nums[i] is either 0 or 1.
- 0 <= k <= nums.length
Intuition
Max consecutive ones iii finds the longest run of 1s obtainable by flipping at most k zeros. The phrase at most k against a contiguous run is the sliding-window signature.
The reframing that simplifies everything is to stop thinking about flipping:
- A window is valid when it contains at most k zeros — which zeros get flipped never needs deciding.
So only the zero count inside the window matters, not the positions of the zeros or the number of 1s.
Extend the right edge, incrementing the zero count when a 0 enters. While that count exceeds k, shrink from the left, decrementing when a 0 leaves. The answer is the largest valid window seen.
A neat property of this problem is that the window never needs to shrink below its best size. Since the answer is a maximum, the window can be kept non-shrinking: advance the left pointer only one step for each right advance once the limit is exceeded. The final window width is then the answer directly.
That variant confuses people because the window can hold too many zeros temporarily. It stays correct because an invalid window is never recorded as an improvement — it simply slides along until it becomes valid again.
The straightforward version, shrinking with a while loop and recording the maximum, is easier to verify and equally fast.
Both run in O(n): each element enters and leaves the window at most once, and space is O(1) since only a counter is held.
"Flip at most k zeros" is a window whose validity is zeros <= k. You never actually flip anything — you just refuse to let the window contain more than k zeros. Any "change at most k elements" question reduces to counting the changeable elements inside a window.
Approach
Before reading on: price up what counting everything costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(1) space.
Reframe as counting zeros
Which zeros to flip never needs deciding. A window is valid when it holds at most k zeros, so only that count matters — not positions, not the number of 1s.
Extend the right edge
Advance right one position at a time, incrementing the zero count whenever a 0 enters the window.
Shrink when over the budget
While the zero count exceeds k, advance the left pointer, decrementing the count as zeros leave. The window becomes valid again.
Record the maximum
Track the largest valid window width seen. Measuring after the shrink ensures only valid windows are recorded.
Know the non-shrinking variant
The window can be kept from ever shrinking, sliding as a unit once the limit is hit. A temporarily invalid window is never recorded as an improvement, so the final width is the answer.
Cost of the scan
Each element enters and leaves the window once, giving O(n) time and O(1) space — a single counter regardless of input size.
Solution & live demo
Common pitfalls
Decrementing zeros for every element leaving the window
left += 1 zeros -= 1
if nums[left] == 0:
zeros -= 1
left += 1Only zeros contribute to the counter, so removing a 1 must leave it untouched. Decrementing unconditionally drives the count negative and lets the window swallow far more than k zeros.
Actually mutating the array
nums[i] = 1 flips += 1
if v == 0:
zeros += 1Flipping in place destroys the information needed when the window's left edge passes back over that index, so the count can never be undone. Counting instead of mutating keeps every step reversible.
Shrinking on zeros >= k
while zeros >= k:
while zeros > k:
Exactly k zeros is allowed — that's the budget, not the limit to stay under. The strict version shrinks one step too early and reports answers consistently short by one flip's worth.
Edge cases
The window may hold no zeros, which degenerates to the plain longest run of 1s.
The whole array is flippable, so the answer is n.
The answer is k, capped by the array length.
No window exists and 0 is returned.