Max Consecutive Ones III — Sliding Window with K Flips [Google, Meta Medium]

Problem Statement#

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example 1:

Input:  nums = [1,1,1,0,0,0,1,1,1,1,0],  k = 2
Output: 6
Explanation: Flip the two zeros at indices 5 and 10.
             The longest run of 1s becomes [1,1,1,0,0,1,1,1,1,1,1] → length 6
             (indices 5–10 after flipping index 5 and keeping the rest).
             Actually the optimal window is indices 0–5 if we flip indices 3 and 4,
             giving [1,1,1,1,1,1] → length 6.

Example 2:

Input:  nums = [0,0,1,1,0,0,1,1,1,0,1,1,1,0,0,0],  k = 3
Output: 10
Explanation: Flip the three zeros to maximise the consecutive window.

Constraints:

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

Why This Problem Matters#

LeetCode 1004 is one of those problems that appears simple on the surface — it is a Medium, it is a binary array, and it is a classic sliding window — but it is a favourite at Google and Meta precisely because it tests whether you can reason about variable-width windows and think carefully about edge cases. Both companies routinely use it as a filter in phone screens before advancing candidates to the full loop.

Beyond the interview context, the underlying pattern — "find the longest subarray satisfying some constraint by maintaining a window with a counted resource" — appears everywhere in production code. Rate limiting systems track "allow at most k violations in any sliding window of N seconds." Quality pipelines compute "the longest segment of data where error rate stays below a threshold." Video streaming algorithms find "the longest buffer window where packet loss does not exceed a budget." Every one of these is structurally identical to this problem.

The reason this problem is worth studying carefully rather than just memorising a template is that it has three subtly different levels of insight. The first level is recognising "sliding window with a zero counter." Most candidates who have done LeetCode get there. The second level is understanding why the window never needs to shrink below its current maximum size — an observation that leads to a cleaner O(n) solution without an inner while loop. The third level is handling the follow-up questions: what if you can flip 1s to 0s, what if k equals the array length, and what if the array arrives as a stream? We cover all three levels here.

The Sliding Window Insight#

The brute-force approach to this problem would enumerate every subarray, count its zeros, and return the longest subarray whose zero count is at most k. That is O(n^2) time — too slow for n up to 100,000.

The key observation that unlocks the linear-time solution is this:

We are looking for the longest contiguous subarray that contains at most k zeros.

Flipping a zero does not change the array — it is just a mental model. The real question is: what is the longest window [left, right] where zeros_in_window <= k? Every zero in that window represents a "flip" we are using; as long as we have k or more flips budgeted, we can include zeros freely.

This immediately suggests a variable sliding window:

1. Expand the right pointer freely, counting zeros as we go.
2. When zeros in the window exceeds k, the window is invalid. Shrink from the left until it is valid again (or just advance the left pointer by one position if we care only about length, not the actual subarray).
3. At every step, the window size right - left + 1 is a candidate answer.

There is a beautiful optimisation here. Because we only care about the maximum length, the left pointer never needs to move back. If we ever shrink the window, the best we can do is tie the current maximum — we can never exceed it unless the right pointer finds a new element that extends beyond it. This means we can replace the inner while loop with a single if statement, reducing code complexity while preserving correctness. The window becomes "sticky at its maximum size."

Think of it like a growing worm: the head (right pointer) always advances one step per iteration. The tail (left pointer) only moves when the window has too many zeros, and it moves exactly one step — just enough to potentially drop one zero. The worm never shrinks; it just stops growing when conditions are bad and resumes growing when it encounters the right values.

Visual Dry Run#

Let us trace through Example 1 step by step.

nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
        0  1  2  3  4  5  6  7  8  9  10
k = 2
 
State: left=0, zeros=0, maxLen=0
 
right=0  nums[0]=1  zeros=0  window=[0..0] len=1  maxLen=1
right=1  nums[1]=1  zeros=0  window=[0..1] len=2  maxLen=2
right=2  nums[2]=1  zeros=0  window=[0..2] len=3  maxLen=3
right=3  nums[3]=0  zeros=1  window=[0..3] len=4  maxLen=4
right=4  nums[4]=0  zeros=2  window=[0..4] len=5  maxLen=5
right=5  nums[5]=0  zeros=3  ← zeros > k=2!
           nums[left=0]=1 → shrink: left=1, zeros stays at 3 (no zero dropped)
           window=[1..5] len=5  maxLen=5
right=6  nums[6]=1  zeros=3  ← still > k!
           nums[left=1]=1 → shrink: left=2, zeros still 3
           window=[2..6] len=5  maxLen=5
right=7  nums[7]=1  zeros=3  ← still > k!
           nums[left=2]=1 → shrink: left=3, zeros still 3
           window=[3..7] len=5  maxLen=5
right=8  nums[8]=1  zeros=3  ← still > k!
           nums[left=3]=0 → shrink: left=4, zeros=2  ✓ valid again
           window=[4..8] len=5  maxLen=5
right=9  nums[9]=1  zeros=2  window=[4..9] len=6  maxLen=6  ← new max!
right=10 nums[10]=0 zeros=3  ← > k!
           nums[left=4]=0 → shrink: left=5, zeros=2  ✓
           window=[5..10] len=6  maxLen=6
 
Final answer: 6  ✓

Notice how the window expands to length 6 at right=9 and holds there. The optimal window is [4..9] which contains exactly 2 zeros (at indices 4 and 5) and four 1s (at indices 6, 7, 8, 9) — six elements total with two flips used.

Also notice the "sticky" behaviour: from right=5 through right=8, the left pointer chases the right pointer step for step, keeping the window at length 5 rather than shrinking it. The window never gets shorter than 5. This is the "no inner while loop" insight made visible.

Common Mistakes#

Mistake 1: Using a while loop to shrink — works but misses the insight#

The most common correct implementation uses an inner while loop:

while zeros > k:
    if nums[left] == 0:
        zeros -= 1
    left += 1

This is perfectly valid and produces the right answer. But it is O(n) amortised, not obviously O(n) at a glance, and it misses the cleaner insight: we only care about maximum length. The if version is simpler and immediately O(n) without amortised reasoning. In an interview, presenting the if version and explaining why it works demonstrates deeper understanding.

Mistake 2: Off-by-one in window length#

The window length is right - left + 1, not right - left. Both pointers are inclusive. A very common mistake is computing right - left and returning a result that is one short. If you get the right answer minus one on every test case, this is almost always the culprit.

Mistake 3: Not handling the edge case where k equals the array length#

When k >= len(nums), you can flip every zero, so the answer is always len(nums). The sliding window handles this naturally (zeros will never exceed k), but many candidates forget to reason about this case and over-complicate their shrink logic. Run through k=5, nums=[0,0,0,0,0] mentally before your interview to confirm your solution returns 5, not 0 or some other value.

Mistake 4: Mutating the input array#

Some candidates try to actually flip the zeros: setting nums[right] = 1 when they "use" a flip, then undoing it when the window shrinks. This is unnecessary, error-prone, and introduces bugs when you try to restore the original value. The sliding window works entirely with a single integer zeros counter — you never need to touch the array values at all.

Mistake 5: Confusing this with Max Consecutive Ones II (LC 487)#

LC 487 is k=1 with an added constraint: you can only flip one zero, but you are asked for the longest window. The same algorithm works, but candidates sometimes remember "LC 487 = sliding window" and then forget to generalise the zero counter when k > 1. Always confirm with the interviewer: is k always 1, or can it vary?

Solutions#

Approach 1: Sliding Window with if (Optimal — recommended in interviews)#

This is the cleanest version. The left pointer never moves backward; the window is "sticky" at its maximum. When zeros > k, we advance left by exactly one — potentially dropping a zero if nums[left] == 0. The window size never decreases, which means right - left + 1 at the end is the answer.

Python#

from typing import List
 
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0          # left boundary of the sliding window
        zeros = 0         # count of zeros currently inside the window
 
        for right in range(len(nums)):
            # Expand the window by including nums[right]
            if nums[right] == 0:
                zeros += 1    # one more zero consumed from our k budget
 
            # If we have used more than k flips, slide the window forward.
            # We use 'if' (not 'while') because the window is sticky —
            # we never want the window to shrink below its current max size.
            if zeros > k:
                # Drop the leftmost element and shrink from the left
                if nums[left] == 0:
                    zeros -= 1    # we freed one zero by removing nums[left]
                left += 1         # advance left boundary regardless
 
        # The window size at the end equals right - left + 1.
        # Since right == len(nums) - 1 after the loop:
        return len(nums) - left

JavaScript#

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function longestOnes(nums, k) {
    let left = 0;    // left boundary of the sliding window (inclusive)
    let zeros = 0;   // number of zeros currently inside [left..right]
 
    for (let right = 0; right < nums.length; right++) {
        // Expand: include nums[right] in the current window
        if (nums[right] === 0) {
            zeros++;    // one flip consumed
        }
 
        // If we exceeded the flip budget, shift the window forward by one.
        // Using 'if' instead of 'while' keeps the window at maximum size —
        // it never shrinks, only slides.
        if (zeros > k) {
            if (nums[left] === 0) {
                zeros--;    // the element leaving the window was a zero
            }
            left++;         // move left boundary one step right
        }
    }
 
    // After the loop, right == nums.length - 1.
    // The maximum window length is the current window size: nums.length - left.
    return nums.length - left;
}

Approach 2: Sliding Window with while (Classic — also correct)#

This version explicitly shrinks the window until it is valid again. It is easier to arrive at under pressure because it mirrors the direct problem statement ("keep shrinking until zeros <= k"). The time complexity is O(n) amortised because each element enters and exits the window at most once.

Python#

from typing import List
 
class Solution:
    def longestOnes_while(self, nums: List[int], k: int) -> int:
        left = 0          # left boundary
        zeros = 0         # zeros in current window
        best = 0          # best window length seen so far
 
        for right in range(len(nums)):
            # Step 1: Expand the window to include nums[right]
            if nums[right] == 0:
                zeros += 1
 
            # Step 2: Shrink from the left until the window is valid (zeros <= k)
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1    # removed a zero from the window
                left += 1         # shrink from the left
 
            # Step 3: Record the best window size seen so far
            best = max(best, right - left + 1)
 
        return best

JavaScript#

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function longestOnes_while(nums, k) {
    let left = 0;    // left pointer
    let zeros = 0;   // zero count in [left..right]
    let best = 0;    // best window length
 
    for (let right = 0; right < nums.length; right++) {
        // Expand: include nums[right]
        if (nums[right] === 0) {
            zeros++;
        }
 
        // Shrink: while window is invalid (too many zeros), move left forward
        while (zeros > k) {
            if (nums[left] === 0) {
                zeros--;    // a zero left the window
            }
            left++;
        }
 
        // Update best: current window is always valid here
        best = Math.max(best, right - left + 1);
    }
 
    return best;
}

Approach 3: Prefix Sum + Binary Search (O(n log n) — for discussion only)#

This approach converts the problem into: "find the longest subarray where the sum of zeros is at most k." Compute a prefix sum of zeros, then for each right index, binary search for the smallest left index such that prefix[right+1] - prefix[left] <= k. This is O(n log n) time and O(n) space — strictly worse than the sliding window. Its value is in demonstrating knowledge of alternative approaches during an interview, especially if asked about generalising to non-binary arrays.

from typing import List
import bisect
 
class Solution:
    def longestOnes_prefix(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # prefix[i] = number of zeros in nums[0..i-1]
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + (1 if nums[i] == 0 else 0)
 
        best = 0
        for right in range(n):
            # We want the leftmost 'left' such that prefix[right+1] - prefix[left] <= k
            # i.e., prefix[left] >= prefix[right+1] - k
            target = prefix[right + 1] - k
            # Binary search for the leftmost index where prefix[left] >= target
            left = bisect.bisect_left(prefix, target)
            # Window is nums[left..right], length = right - left + 1
            best = max(best, right - left + 1)
 
        return best

Complexity Analysis#

The sliding window approaches are optimal: no algorithm can do better than O(n) because every element must be examined at least once. The O(1) space bound holds because we track only two pointers and one counter regardless of input size.

Follow-up Questions#

These are questions that interviewers at Google and Meta actually ask immediately after a candidate solves this problem. Prepare answers to all of them.

Follow-up 1: What if you can flip 1s to 0s instead — find the longest run of 0s?#

The algorithm is symmetric. Count 1s in the window instead of zeros. When ones > k, shrink from the left. Everything else is identical.

# Same algorithm; just swap the zero check with a ones check
if nums[right] == 1:
    ones += 1
if ones > k:
    if nums[left] == 1:
        ones -= 1
    left += 1
return len(nums) - left

Follow-up 2: What if the array is a stream (you cannot look ahead)?#

The while-loop version works naturally on a stream: process one element at a time, maintain the window, emit the current window size. The if-version also works because it never looks ahead. Both are online algorithms. The prefix sum approach requires the full array upfront and cannot be used.

Follow-up 3: What if instead of a binary array, each element has a "cost to flip" and you have a total budget B?#

This is a more general version where you replace the zero counter with a budget counter. Maintain cost_in_window = sum of flip costs for all zeros in [left..right]. When cost_in_window > B, shrink from the left. This requires storing the cost of each element left in the window, which can be read directly from the array — the rest of the algorithm is unchanged. Time is still O(n), space is still O(1).

Follow-up 4: What if you want to return the actual subarray (not just its length)?#

Track the left pointer at the moment you record the best length. At the end, the answer subarray is nums[best_left : best_left + best_length].

best_left = 0
best_len = 0
# ... (same sliding window loop)
# When you update best:
if right - left + 1 > best_len:
    best_len = right - left + 1
    best_left = left
# Return:
return nums[best_left : best_left + best_len]

Follow-up 5: What if k is 0?#

When k=0, no flips are allowed. The problem reduces to "find the longest consecutive run of 1s" — LeetCode 485. The same sliding window algorithm handles this correctly: zeros will exceed k=0 the moment any zero is encountered, and left will chase right through every zero block.

Follow-up 6: Can you solve this in a single pass without the if/while distinction?#

Yes. The if-version is already a single forward pass where every pointer moves forward exactly once. This is already optimal. The interviewer may be probing whether you understand that the if-version is O(n) worst-case (not just amortised), while the while-version is O(n) amortised.

This Pattern Solves#

The variable sliding window with a "budget counter" appears across a wide family of problems. Recognising it as a pattern — rather than memorising each problem individually — is what makes preparation efficient.

The common template is: expand right freely, track a "resource" that the window consumes, and shrink from the left when the resource is exhausted. The resource here is flip budget. The window validity condition is resource_used <= k.

Key Takeaways#

• LeetCode 1004 — Max Consecutive Ones III is a Medium asked at Google and Meta; it is the canonical variable sliding window problem where k flips govern window validity.
• Sliding window: expand right always, shrink left when zeros in window exceed k — O(n) time, O(1) space versus brute-force O(n^2).
• The "sticky window" optimization: use if (not while) to shrink, because you only care about the maximum length ever seen, not each valid window independently.
• The window never shrinks below its historical maximum — once it reaches a certain size it only slides, never contracts.
• Key invariant: zeros_in_window = right - left + 1 - ones_in_window — track zeros implicitly via window size minus ones count.
• k=0 edge case: only windows of all-ones are valid — the algorithm handles this naturally without special-casing.
• Generalizes to LC 424 (Longest Repeating Character Replacement) where the "budget" is replacements instead of flips — same sliding window template.