Max Consecutive Ones III

You are given a binary array nums (each element is 0 or 1) and an integer k. You may flip at most k zeros to ones.

Return the length of the longest contiguous run of 1s you can produce.

Hints

· Stuck? Reveal one nudge at a time.

Flipping zeros to get a run of ones — what does that run look like as a window?

It's a window containing at most k zeros (all of which you flip).

Grow the window on the right, and shrink from the left whenever it holds more than k zeros.

Common doubts

A window with at most k zeros is achievable by flipping exactly those zeros, so its length is a valid candidate. You only need to count zeros, not perform flips.

The window's feasibility depends solely on how many zeros it contains; the ones are free. The count rises on an entering zero and falls on a departing one.

Then every zero can be flipped and the answer is the whole array length — the window never becomes invalid.

Interview follow-ups

· What an interviewer asks next.

Symmetric — it becomes the longest window with at most k ones; swap which value you count.

A common variant never shrinks the window's size below the current best — it only slides — giving the same answer with one comparison removed.

Fun facts

This is the binary special case of 'longest window with at most k of some bad element' — the same window works for any single forbidden symbol.
The never-shrink variant treats the window like a monotone frontier, a trick reused in streaming max-window computations.

Asked at

AmazonGoogleMicrosoftMeta

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Flip the two zeros at indices 5 and 10... the best window [1,1,1,1,0,0]->flip gives a run of 6.

Example 2

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Flipping three well-chosen zeros yields a run of 10 ones.

Constraints

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

Flipping up to k zeros to ones and asking for the longest run of ones is the same as asking: what's the longest window that contains at most k zeros? Grow the window on the right; whenever it holds more than k zeros, shrink from the left until it's back to k or fewer.

Prerequisites

Before you start

· Concepts used directly in the solution.

Variable-size window. Growing and shrinking a window to keep a condition true.

Window invariant. Here the invariant is "the window contains at most k zeros".

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The operation

“Do I have to flip exactly k zeros?”

No — at most k. Fewer is fine; you just can't exceed k.

“Are the ones and flipped zeros required to be contiguous?”

Yes — the answer is a single contiguous run after flipping.

Reframing

“How does flipping become a window condition?”

A run of ones after flipping is just a window whose zeros (all flipped) number at most k.

The ideal opening — say it like this

The longest run of ones after flipping k zeros is the longest window containing at most k zeros.

I'll extend the right edge and count zeros inside the window.

If the count exceeds k, I shrink from the left until it's back within k, and track the longest valid width.

Understand the problem

Worked example — nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

window grows to [0,0,1,1,1,1] region... at most 2 zeros allowed
best valid window: indices 5..10 -> [0,1,1,1,1,0] has 2 zeros, length 6
answer: 6

Key observations

1Aha

Longest ones = longest window with <= k zeros

Flipping k zeros to ones inside a window makes it all ones, so the achievable runs are exactly the windows containing at most k zeros.

2Aha

Only the zero count matters

You don't track positions of ones — just the number of zeros in the window. It rises on an entering zero and falls on a leaving zero.

3Aha

Shrink only when infeasible

Grow greedily; contract from the left exactly when the zero count exceeds k, and only until it's valid again. Both pointers move forward, so it's O(n).

Brute force vs optimal

	Extend from each start	Sliding window
Idea	From each index, extend while zeros <= k	One window, shrink when zeros exceed k
Time	O(n^2)	O(n)
Space	O(1)	O(1)

The brute restarts the zero count at each index; the window carries it forward, only ever moving both pointers right. Full code is in the Approaches selector below.

Summary

Key takeaway

Reframe "flip at most k zeros for the longest run of ones" as "longest window with at most k zeros". Grow the right edge counting zeros; when the count exceeds k, shrink from the left until it's valid, tracking the longest width. One O(n) pass.

left = 0; zeros = 0; best = 0
for right in 0 .. n-1:
    if nums[right] == 0: zeros += 1
    while zeros > k: if nums[left] == 0: zeros -= 1; left += 1
    best = max(best, right - left + 1)
return best