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.
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
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.