Max Consecutive Ones III: Budgeted Zeros in the Window

This one is a Medium-rated classic reported from Meta, Microsoft, Amazon interviews: "Max Consecutive Ones III". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Sliding Window pattern on sight. Part 8 of 11 in the Sliding Window arc.

The Problem

Given a binary array nums and an integer k, return the length of the longest contiguous run of 1s achievable if you may flip at most k 0s to 1s. The reframe that unlocks it: you never flip anything — you look for the longest window containing at most k zeros.

Input:  nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Output: 6
Window [0, 0, 1, 1, 1, 1] flips its two zeros.

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Allowed to change at most k elements to satisfy a property is a budget constraint in disguise: longest window with at most k violations. The same reframe cracked Character Replacement earlier in this arc — this is its binary special case.

The Approach

Count zeros in the current window. Grow right; when zeros exceed k, advance left (decrementing the count when a zero exits) until the budget is restored. Record the best length each step.

No array mutation, no simulation of flips — just arithmetic on a counter. Saying the reframe sentence first is most of the interview.

Python Solution

def longest_ones(nums: list[int], k: int) -> int:
    """Longest window containing at most k zeros."""
    left = 0
    zeros = 0
    best = 0
    for right, v in enumerate(nums):
        if v == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Complexity

• Time: O(n) — both pointers move forward only
• Space: O(1) — one counter, two indices

Interview Tips and Follow-Ups

• k = 0 degenerates to longest run of 1s — verify your code handles it without special-casing.
• The non-shrinking window trick from Character Replacement applies here too; offer it as an optimization footnote.
• Related screen question: Max Consecutive Ones II (k = 1, premium) — identical code, fixed budget.

More Sliding Window problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.