Max Consecutive Ones III — Variable Sliding Window with K Flips at Google

Problem Statement#

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

Constraints:

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

Input:  nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

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

Why This Problem Matters#

LeetCode 1004 Max Consecutive Ones III is a textbook variable sliding window problem and a Google and Amazon staple. The interview signal is whether the candidate spots that "at most k zeros inside the window" is the invariant that makes the longest-window template work.

The brute force enumerates all O(n^2) subarrays and counts zeros, costing O(n^2) time. The sliding window solution runs in O(n) time and O(1) space, and the difference is precisely what interviewers are listening for.

This problem is the binary cousin of LC 424 Longest Repeating Character Replacement and the sister problem of LC 1493 Longest Subarray of 1s After Deleting One. Once you internalize the at-most-k-zeros invariant, all three become the same template with different per-window state.

The Core Insight#

We want the longest contiguous window with at most k zeros. Use a variable sliding window: expand the right edge, count zeros inside the window, and whenever the zero count exceeds k, shrink the left edge until the count is back to k.

At every step the window is a valid candidate, so we update the answer with right - left + 1. The window expands monotonically; we never move right backwards. The left pointer only advances when the invariant breaks, so each pointer moves at most n times total.

The state inside the window is just one integer: the count of zeros. No hash map is required.

Visual Dry Run#

For nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2:

Return 6.

Solution (Optimal)#

class Solution:
    def longestOnes(self, nums: list[int], k: int) -> int:
        left = 0
        zeros = 0
        best = 0
        for right in range(len(nums)):
            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

var longestOnes = function(nums, k) {
    let left = 0;
    let zeros = 0;
    let best = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeros++;
        while (zeros > k) {
            if (nums[left] === 0) zeros--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
};

Time: O(n) — each pointer moves at most n times Space: O(1) — one counter and two pointers

Common Mistakes#

• Using if instead of while to shrink the window, which leaves the invariant broken
• Updating best before restoring the invariant, capturing an invalid window
• Decrementing zeros on every left advance instead of only when nums[left] == 0
• Re-counting zeros from scratch on each window, costing O(n^2)
• Confusing this with the fixed window template and using a window of size k

Interview Tips#

• State the invariant out loud: "At most k zeros inside the window means the window is achievable with k flips"
• Show that you understand why while is required, not if: a single right move can introduce only one zero, but after shrinking we might still need to shrink again if multiple zeros sit at the left
• Mention LC 1493 as the natural follow-up where exactly k must be deleted
• Clarify that we never explicitly perform the flips; we just count whether they would fit

Follow-up Questions#

• What if you can flip exactly k zeros, not at most? (Hint: same window, harder accounting)
• What if the array is binary but you can flip at most k ones to zeros instead? (Hint: same template, swap roles)
• How would you handle a stream where you cannot revisit nums[left]? (Hint: deque of zero positions)
• What if there are three values: 0, 1, and 2, and you can flip at most k of any? (Hint: count non-target values)
• How does this relate to LC 424 Longest Repeating Character Replacement? (Hint: same variable window, replace character count with frequency map)

Key Takeaways#

• LeetCode 1004 Max Consecutive Ones III is the canonical variable sliding window with a flip budget
• Invariant is at most k zeros inside the window; expand right, shrink left when violated
• O(n) time and O(1) space, no hash map required
• Use while to shrink, not if, to fully restore the invariant
• Pattern extends directly to LC 424 and LC 1493
• Google and Amazon use this problem to test whether candidates spot the variable window template
• Track only the zero count; the actual flips are never performed