STEP 10 · SLIDING WINDOW · SLIDING WINDOW · MEDIUM

Max Consecutive Ones III

WHAT IT SAYS

Given a binary array and a budget k, find the longest stretch of consecutive 1s you can produce by flipping at most k zeros.

WHAT IT'S REALLY ASKING

"Stop thinking about flips. You're buying a stretch of the array, and zeros are the only thing you pay for — so the real question is: as your right hand reaches further, which starting points have already gone over budget, and can a start that's gone over budget ever come back under?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Try every stretch, count its zeros

O(n²) time, O(1) space

For each start i, extend right and keep a running zero count; the moment it exceeds k, this start is done — record the best length reached and restart the whole thing from i + 1. Every candidate stretch gets priced, so correctness is obvious.

WHERE THE WORK IS WASTED — Each restart re-prices a stretch you already priced. The walk from i counted the zeros in s[i+1..r] on its way to r; the walk from i + 1 counts those exact same zeros again, from scratch, and then busts on the exact same zero at r. Every start from i up to the first zero in the window repeats that identical count and dies at the identical place — you're paying O(n) to rediscover a fact the previous pass already established.

KEY OBSERVATION — THE UNLOCKlink

Zeros never leave. A busted start is busted forever.

Zero-count is monotone in the window: extend the right edge and the count can only rise or stay; it can never fall, because the array doesn't change and you never remove anything from the right. So if [i..r] already holds k+1 zeros, then [i..r'] for every r' > r holds at least k+1 zeros too. Start i isn't merely bad right now — it is dead for the rest of the scan, and so is every start before it. The same monotonicity, read from the left, is what makes the fix cheap. Dropping elements off the left can only lower the zero count, so validity is hereditary: if [l..r+1] is affordable then [l..r] was affordable. That means the leftmost surviving start for r+1 can never sit further left than the leftmost surviving start for r. The left edge only ever moves forward. Two pointers, one pass, and the only bookkeeping you need is a single integer: how many zeros are currently inside.

Right pays, left evicts

O(n) time, O(1) space

Walk the right edge forward, adding 1 to the zero count whenever you swallow a zero. While the count exceeds k, advance the left edge, refunding a zero each time you evict one — you'll always stop the moment you pass the earliest zero in the window. Every index enters once and leaves at most once, so the nested-looking loop costs 2n steps, and the answer is the largest window you ever held.

The window that refuses to shrink

O(n) time, O(1) space, one pointer move per index

Since you only care about the maximum, an over-budget window never needs to get smaller — it only needs to stop growing. Replace the inner while with a single if: when the count exceeds k, slide left by exactly one (refunding if it was a zero) so the window's width is preserved, not reduced. The window drifts along at the best width seen so far and only widens when it finds something genuinely better, which is why the answer is just the final width — no max() tracking required.

WHAT YOU TRADED — Nothing is exchanged here but generality: the whole thing rests on the cost of a window being monotone in its width, so the left edge is safe to never rewind. Change the constraint to something non-monotone — 'at most k zeros but an even number of ones', say — and shrinking from the left can turn an invalid window valid, the left edge is forced backwards, and the sliding window quietly degenerates into the brute force it was pretending not to be.

WATCH THE IDEA RUN

width 0

best 0

zeros spent / 2 0

Budget: flip at most 2 zeros. Right will walk the whole array once. Watch what the left edge does — and what it never does.

step 1 / 22

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Budgeted Window

YOU'LL SEE IT AGAIN WHEN

You want the longest contiguous stretch subject to a budget, and the cost of a stretch only grows as you extend it — never falls.
The constraint is violated by identifiable elements you can point to, so when a window busts you know exactly which starts busted with it.
Brute force would restart from each index and re-tally a cost it just finished tallying one index earlier.
The cost can be updated in O(1) as a single element enters or leaves the window.

SAME BLUEPRINT, DIFFERENT PROBLEM

Longest Repeating Character ReplacementFruit Into BasketsLongest Substring with At Most K Distinct CharactersMax Consecutive Ones II

The bar isn't "solved it once." It's "could rebuild it from the observation."