Max Consecutive Ones III

SLIDING WINDOW · MEDIUM

The problem

You’re given a binary array nums (every value is 0 or 1) and an integer k. You’re allowed to flip at most k of the 0s to 1s — anywhere in the array, your choice which ones. After flipping, return the length of the longest contiguous run of 1s you can produce. You never have to actually perform the flips; you just need the length of the best window. For example, nums = [1,1,1,0,0,0,1,1,1,1,0] with k = 2 gives 6: the window nums[4..9] = [0,0,1,1,1,1] contains exactly 2 zeros, both flippable within budget, producing a run of 6 ones — and no window with ≤ 2 zeros is longer than that.

Solution 1: Brute force — every subarray, re-counted from scratch

The most literal reading of the problem: try every possible contiguous subarray nums[start..end], and for each one, scan it to count how many zeros it contains. If that count is within budget (<= k), it’s a candidate — keep it if it’s the longest one seen so far. There’s no memory carried between subarrays; each one is re-examined completely independently, which is exactly what makes this slow.

Interactive visualization

nums = [1, 1, 0, 0, 1, 1, 1, 0], k = 2 — valid window (zeros ≤ k), not the longest yet: compare · new longest found: active · too many zeros: swap · best found: sorted

Press Play or Step to begin.

Step 0 / 38

This animation traces nums=[1,1,0,0,1,1,1,0], k=2 (node-verified answer: 7, window [0..6]) — a smaller example than the LeetCode one above, kept small on purpose since O(n³) generates a lot of subarrays to check.

The code

function longestOnesBrute(nums, k) {
  const n = nums.length;
  let best = 0;

  for (let start = 0; start < n; start++) {
    for (let end = start; end < n; end++) {
      let zeros = 0;
      for (let i = start; i <= end; i++) {
        if (nums[i] === 0) zeros++;
      }
      if (zeros <= k) {
        best = Math.max(best, end - start + 1);
      }
    }
  }
  return best;
}

Line by line:

The outer two loops enumerate every (start, end) pair with start <= end — that’s every contiguous subarray, O(n²) of them.
The innermost loop counts zeros in nums[start..end] by scanning it index by index — O(n) work, and it starts completely fresh for every single pair, even though most of it overlaps with the previous pair’s window.
if (zeros <= k) is the only place the flip budget is enforced — a window with more zeros than k can flip is simply never a candidate.
best = Math.max(best, end - start + 1) only updates when a window is both valid and longer than anything seen so far.

Complexity

Time	Space	Approach
O(n³)	O(1)	O(n²) subarrays, each re-counting its zeros in a fresh O(n) scan

Solution 2: Optimal — variable-size sliding window tracking zero count

Instead of re-counting zeros for every window from scratch, keep a single running zeroCount for the current window [left, right] and update it incrementally. Expand right across the array one step at a time; every time the new element is a zero, increment zeroCount. Whenever zeroCount exceeds k, the window has become invalid — shrink it from the left (decrementing zeroCount only if the element leaving was itself a zero) until it’s valid again. The window’s bounds never reset: left only ever moves forward, so this explores every valid window without ever re-examining the same element from scratch.

Interactive visualization

nums = [1, 1, 0, 0, 1, 1, 1, 0], k = 2 — right pointer expanding: pointer · current window: active · over budget check: compare · left shrinking: swap · best found: sorted

Press Play or Step to begin.

Step 0 / 23

Same nums=[1,1,0,0,1,1,1,0], k=2 as Solution 1 (node-verified answer: 7), so you can compare step counts directly — notice how few steps this takes compared to the brute-force trace above.

The code

function longestOnesOptimal(nums, k) {
  let left = 0;
  let zeroCount = 0;
  let best = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeroCount++;

    while (zeroCount > k) {
      if (nums[left] === 0) zeroCount--;
      left++;
    }

    best = Math.max(best, right - left + 1);
  }
  return best;
}

Line by line:

left and zeroCount persist across the entire loop — nothing resets between iterations of right, which is exactly the memory the brute force throws away every single pair.
if (nums[right] === 0) zeroCount++ is an O(1) incremental update, replacing the brute force’s O(n) re-scan with a single comparison.
The while (zeroCount > k) loop only runs when the window is currently invalid, and each iteration moves left forward exactly once — it can never run more times in total than left has room to advance, which is at most n across the whole function (the classic sliding-window amortized argument: right advances n times, left advances at most n times, so total work is O(n) even though there’s a loop nested inside a loop).
best = Math.max(best, right - left + 1) runs once per right, always measuring a window that’s already valid at that point — the shrink loop above it guarantees that.

Complexity

Time	Space	Approach
O(n)	O(1)	Each pointer advances forward at most n times total — amortized linear, no re-scanning

Complexity comparison

Solution	Time	Space
Brute force (every subarray, re-scanned)	O(n³)	O(1)
Optimal (sliding window, running zero count)	O(n)	O(1)

This is a genuinely dramatic gap, not a same-complexity relabeling: the brute force re-examines overlapping windows from scratch (O(n²) windows × O(n) scan each), while the optimal solution never looks at any element more than a constant number of times — each index is added to the window exactly once (by right) and removed at most once (by left). Both use O(1) extra space; the only thing that changes is how much redundant work gets thrown away between iterations.

Interview corner

Q: Why is it safe for left to only ever move forward, never back up to re-check an earlier position?

The window is defined by two facts: left is the earliest index that keeps zeroCount <= k, and every index before it was already ruled out as part of the current best window ending at the current right.
As right only increases, the window can only need to shrink further (more zeros could enter), never less — so once an index has been excluded because it made the window invalid, adding more elements to the right can’t make that same exclusion unnecessary.
That monotonic relationship is exactly what makes the amortized O(n) bound work: both pointers move strictly forward, so their combined movement is bounded by 2n, not n².

Q: Why is tracking a single running zeroCount integer correct, instead of recomputing the zero count of the window every time it changes?

The window only ever changes by one element at a time — either right adds exactly one new index, or the shrink loop removes exactly one index at left.
Since nums only contains 0s and 1s, the effect of adding or removing a single element on the zero count is fully known in O(1): +1 if it’s a zero entering, -1 if it’s a zero leaving, no change otherwise.
Recomputing from scratch would give the same answer, just slower — the incremental update is provably equivalent to the brute force’s fresh scan, applied one element at a time instead of the whole window at once.

Q: How would the approach change if the problem asked for a window with exactly k zeros flipped, instead of at most k?

The core expand/shrink mechanics stay identical — the change is only in which windows count as valid answers.
“At most k” lets every valid window (0 through k zeros) compete for the longest length, so the window naturally grows as large as the budget allows.
“Exactly k” would need the shrink condition to also fire when zeroCount drops below k in a way that’s no longer extendable to exactly k — in practice this is usually solved as atMost(k) - atMost(k - 1) (count windows with at most k zeros, subtract windows with at most k-1), reusing this exact function twice rather than rewriting the window logic.

↳ Common follow-up: “Could you solve ‘exactly k’ with a single pass instead of two calls to ‘at most k’?” It’s possible with extra bookkeeping, but the two-call reuse is the standard answer because it’s provably correct by construction and doesn’t require re-deriving a new invariant.

Q: Trick question — what does this log?

let zeroCount = 5, k; // k was never assigned
console.log(zeroCount > k);

Answer: false — not true, and it does not throw.
k is undefined, and any relational comparison (>, <, >=, <=) coerces its operands to numbers first — undefined becomes NaN, and every comparison involving NaN evaluates to false, including NaN === NaN.
Node-verified: 5 > undefined, 0 > undefined, and 0 <= undefined are all false.

⚠️ Trap: this is exactly the line the optimal solution’s shrink loop depends on — while (zeroCount > k). If k were ever accidentally undefined (a typo’d parameter name, a missing argument), that while condition would silently evaluate to false every time instead of throwing an error — the shrink loop would simply never run, and the function would return a wrong (too-large) answer with no crash to point at the bug.

Quiz

1. Why can left only ever move forward in the optimal solution, never back up?

Because right only increases, the window can only need to shrink further, never less — excluded indices stay excluded
It’s purely a performance choice with no effect on correctness — moving it backward would still work
It’s an arbitrary implementation convention, not something the algorithm depends on

Answer

Because right only increases, the window can only need to shrink further, never less — excluded indices stay excluded. Since right only increases, the window can only need to shrink further (more zeros could enter), never less — so once an index has been excluded because it made the window invalid, adding more elements to the right can’t make that same exclusion unnecessary.

2. Why is it correct to update zeroCount with +1/-1 instead of recomputing it from scratch each time the window changes?

The window only ever changes by exactly one element at a time, so the effect on the zero count is always knowable in O(1)
It’s an approximation that’s usually close enough, traded for speed
Because nums is guaranteed to contain at least one 1, which makes recomputation unnecessary

Answer

The window only ever changes by exactly one element at a time, so the effect on the zero count is always knowable in O(1). The window only ever changes by one element at a time — either right adds exactly one new index, or the shrink loop removes exactly one index at left. Since nums only contains 0s and 1s, the effect of adding or removing a single element on the zero count is fully known in O(1): +1 if it’s a zero entering, -1 if it’s a zero leaving, no change otherwise.

3. The optimal solution has a while loop nested inside a for loop. Why is the total time still O(n), not O(n²)?

left can advance at most n times total across the whole function (not per outer iteration), so the two pointers together do O(n) combined work
The while loop is skipped entirely in almost all real inputs, so its cost doesn’t matter
The JavaScript engine automatically optimizes nested loops with a shared counter variable

Answer

left can advance at most n times total across the whole function (not per outer iteration), so the two pointers together do O(n) combined work. The while loop is nested inside the for loop, but left can advance at most n times in total across the ENTIRE run of the function, not per iteration of right. Summed over the whole function, right’s n steps plus left’s at-most-n steps give O(n) total work, not O(n²).

4. What specifically makes the brute-force solution O(n³) instead of O(n²)?

Each of the O(n²) subarrays pays its own fresh O(n) zero-count scan, with nothing reused between overlapping windows
It sorts the array before checking each subarray, adding an extra O(n log n) factor
It uses recursive backtracking to explore every possible flip combination

Answer

Each of the O(n²) subarrays pays its own fresh O(n) zero-count scan, with nothing reused between overlapping windows. The brute force re-counts zeros for every one of its O(n²) subarrays with a fresh O(n) scan, even though most of each window overlaps with the previous one. That’s O(n²) x O(n) = O(n³) work with nothing carried between windows — the exact redundancy the optimal solution’s running zeroCount eliminates.

5. If k in while (zeroCount > k) were accidentally undefined, what happens?

The comparison silently evaluates to false (undefined coerces to NaN, and all NaN comparisons are false) — no error, the loop just never runs
JavaScript throws a TypeError immediately, since undefined can’t be compared with a number
The while loop runs forever, since undefined is treated as infinitely large

Answer

The comparison silently evaluates to false (undefined coerces to NaN, and all NaN comparisons are false) — no error, the loop just never runs. undefined becomes NaN, and any comparison involving NaN — including NaN === NaN — evaluates to false. So zeroCount > k silently becomes false instead of throwing, and the shrink loop that depends on it would simply never run, and the function would return a wrong (too-large) answer with no crash to point at the bug.