Max Consecutive Ones III Solution

Problem

Given a binary array and an integer k, find the longest contiguous subarray of 1s you can form by flipping at most k zeros to 1s. You are maximizing the window length, not counting how many flips you use.

Example:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: Flip the zeros at indices 4 and 5; the window [0,0,1,1,1,1] becomes six consecutive 1s.

Counter-example: With k = 1, the longest valid window is 5 — there are 3 zeros in the array so you cannot bridge all the gaps at once, and the best single flip extends one contiguous group by one.

Intuition

Flipping at most k zeros is the same as asking: what is the longest window that contains at most k zeros? Instead of checking all O(n²) windows, a sliding window keeps this constraint satisfied dynamically — expand the right boundary greedily, and shrink the left boundary only when the zero count exceeds k. Since both pointers only move rightward, the total work is O(n).

Approach 1 — Brute Force

Try every possible starting position and extend right as far as the flip budget allows.

Steps:

For each left index, reset zero_count to 0
Extend right from left to the end of the array
If nums[right] is 0, increment zero_count
If zero_count exceeds k, stop extending this window
Otherwise update max_length with right - left + 1
Return max_length

1class Solution:
2    def longestOnes(self, nums: List[int], k: int) -> int:
3        max_length = 0
4        n = len(nums)
5        for left in range(n):
6            zero_count = 0
7            for right in range(left, n):
8                if nums[right] == 0:
9                    zero_count += 1
10                if zero_count > k:
11                    break  # exceeded flip budget; no valid extension from this left
12                max_length = max(max_length, right - left + 1)
13        return max_length

Time: O(n²) — for each of n starting positions, the inner loop scans up to n elements
Space: O(1) — only a constant number of integer variables

Approach 2 — Sliding Window

Maintain a window [left, right] that always contains at most k zeros. Expand right one step at a time; when the zero count exceeds k, advance left until the window is valid again.

Steps:

Initialize left = 0, zero_count = 0, max_length = 0
For each right, if nums[right] is 0 increment zero_count
While zero_count > k, if nums[left] is 0 decrement zero_count, then advance left
Update max_length with right - left + 1
Return max_length

1class Solution:
2    def longestOnes(self, nums: List[int], k: int) -> int:
3        left = 0
4        zero_count = 0
5        max_length = 0
6        for right in range(len(nums)):
7            if nums[right] == 0:
8                zero_count += 1
9            while zero_count > k:
10                if nums[left] == 0:
11                    zero_count -= 1  # un-count the zero being evicted from the window
12                left += 1
13            max_length = max(max_length, right - left + 1)
14        return max_length

Time: O(n) — both left and right only ever advance forward, so each element is visited at most twice
Space: O(1) — only three integer variables regardless of input size

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Only as an interview starting point to establish the core insight
Sliding Window	O(n)	O(1)	Always — both pointers traverse the array once; this is the standard solution

Common Mistakes

Off-by-one in window length — the window [left..right] has right - left + 1 elements, not right - left; consistently using the latter underestimates every window by 1 and produces a wrong answer even on the simplest input.
Re-scanning the window to count zeros — computing something like nums[left:right+1].count(0) inside the loop creates a new slice and runs in O(n) per step, making the total O(n²) and defeating the purpose of the sliding window; maintain zero_count incrementally instead.
Breaking the outer loop when zero_count > k — when the budget is exceeded you need to shrink left, not abandon the rest of the array; valid windows starting at later positions can still extend further than anything seen so far.
Forgetting to decrement zero_count when evicting nums[left] — when left advances past a zero, that zero leaves the window and must be subtracted from zero_count before left increments; skipping this causes zero_count to be artificially high and forces left to overshoot the correct position.
Confusing "at most k zeros" with "exactly k zeros" — a window with fewer than k zeros is perfectly valid and may be the longest; the shrink condition is zero_count > k, not zero_count != k.

Max Consecutive Ones III — Solution