1004. Max Consecutive Ones III

1004

MediumSliding WindowSliding window with a counter of forbidden elementsLongest window with a bounded budget of flips

Max Consecutive Ones III

Given a binary array nums and an integer k, you may flip at most k zeros to ones. Return the length of the longest contiguous subarray containing only ones after performing at most k flips.

Open official problem prompt ↗

In plain English

Find the longest stretch of the array that can be made all-ones by flipping no more than k of its zeros.

Picture it like this

You are painting a fence and have only k patches of white paint for the dark boards. You want the longest continuous section of fence you can make fully white — slide a frame along the fence, and whenever it swallows a (k+1)th dark board, pull the back edge forward until you are back within your paint budget.

Example

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Why: Flipping the two zeros at indices 4 and 5 turns nums[4..9] = [0,0,1,1,1,1] into six consecutive ones, giving length 6; no window of length 7 works because every 7-element window contains at least three zeros.

Constraints

1 <= nums.length <= 10^5nums[i] is 0 or 10 <= k <= nums.length

Pattern lesson

See the pattern, then code

Longest window with a bounded budget of flips

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Let the window contain at most k zeros. Grow the right edge freely; whenever the zero count exceeds k, slide the left edge forward until the budget is restored. The largest window ever seen is the answer, because every zero inside can be flipped.

New words, made simpleKnow these before the algorithm

Flip budget: The at-most-k zeros you are allowed to turn into ones inside the current window.
Window validity: A window is valid when its zero count is <= k, meaning it can be fully converted to ones.
Monotonic shrink: Once too many zeros enter, left only moves forward, never back, keeping the whole scan linear.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check every subarray

With n up to 10^5 this is far too slow.

For each start and end, count zeros and test against k.

Time O(n^2)Space O(1)

Best choiceSliding window on zero count

Each element enters and leaves the window at most once.

Maintain a window whose zero count never exceeds k, shrinking from the left when it does.

Time O(n)Space O(1)

The rule we keep true

Invariant

After processing each right, the window [left, right] contains at most k zeros, and best holds the maximum length of any valid window seen so far.

Why this is correct

Reasoning

Any window with at most k zeros can be turned entirely into ones by flipping those zeros, so its length is achievable. The algorithm never lets the window hold more than k zeros, and it tries every right endpoint with the smallest possible left, so it examines the longest valid window ending at each position. The overall maximum is therefore the true answer.

The algorithm in three movesSay these aloud before coding

1Move right across the array, incrementing a zeros counter when nums[right] is 0

right=8: window=[4..8], zeros=2, len=5

2While zeros exceeds k, advance left, decrementing zeros when the element leaving is a 0

right=9: window=[4..9], zeros=2, len=6 -> best=6

3After each step the window is valid; update best with right - left + 1

right=10: nums[10]=0 makes zeros=3, shrink left to 5 -> window=[5..10], len=6

4Return best

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

010

1 · Readidx0-2 read 1,1,1

2 · Askzeros<=k?

3 · Update stateleft=0, zeros=0

4 · Resultbest=3

Key takeaway

The window at indices 4-9 holds exactly two zeros (idx4, idx5) — the flip budget — followed by four ones, giving length 6.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Initialize
left marks the window start, zeros counts zeros inside it, best is the answer so far.
2
Lines 6-8Extend right and count zeros
Each new element is admitted; a zero consumes one unit of flip budget.
3
Lines 9-12Restore the budget
While zeros exceeds k, walk left forward, refunding a unit each time a zero leaves the window.
4
Lines 13Record the best length
The window is now valid, so its length right - left + 1 is a candidate answer.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k = 0 (no flips): reduces to the longest run of existing ones
k >= number of zeros: the whole array qualifies, answer is n
All zeros with k < n: answer is exactly k
Single-element array

Common beginner mistakes

Using an if instead of a while to shrink — with a binary array one shrink step per addition suffices, but the while form is the safe, general pattern
Forgetting to only decrement zeros when the departing element is actually 0
Returning left/right pointers instead of the max window length

Check your understanding

If k = 0, what does this algorithm compute?

Max Consecutive Ones III

Max Consecutive Ones III

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window