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.
Open on LeetCode ↗Intuition
The trap is trying to simulate the flips: pick which zeros to flip, then measure the run. You never actually flip anything. A window of 1s-after-flipping-k-zeros is achievable exactly when the window contains at most k zeros, so the problem is really "longest window with at most k zeros" wearing a costume. Once you restate it that way, it is the standard grow-then-shrink template, not a simulation problem at all.
"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
Restate the flipping as a counting constraint
You never actually need to flip anything. A window is achievable exactly when the number of zeros inside it is at most k, so the answer is the widest such window. This restatement is the whole trick — the brute force of trying every subarray and counting its zeros is O(n^2) and does no more work conceptually.
Grow right, shrink left
Advance right one step at a time, incrementing zeros whenever nums[right] == 0. If zeros > k the window is now illegal, so advance left, decrementing zeros when the element leaving is a zero. Because both pointers only ever move forward, the total work is O(n) despite the nested-looking loops.
Record the answer after every legal state
Once the inner shrink loop finishes, the window is valid again, so update best = max(best, right - left + 1). Note that the shrink is a while, not an if — that distinction matters in the variants where a single step out can remove more than one unit of the constraint, and keeping it a while here means the same template transfers unchanged. O(n) time, O(1) space.
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.