Max Consecutive Ones III

Problem

You are given a binary array nums (each element is 0 or 1) and an integer k. You may flip at most k zeros into ones. Return the length of the longest run of consecutive 1s achievable after the flips.

Reworded without flipping: find the longest contiguous subarray that contains at most k zeros — flipping exactly those zeros makes it all ones.

Examples

• nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2 → 6 — flip the zeros at indices 5 and 10, making indices 5–10 six consecutive 1s (flipping indices 4 and 5 instead also yields a run of 6).
• nums = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], k = 3 → 10 — flip the zeros at indices 4, 5, and 9 to connect indices 2–11.
• nums = [0, 0, 0], k = 0 → 0 — no flips allowed and no 1s present.

Constraints

• 1 <= len(nums) <= 10^5
• nums[i] is 0 or 1
• 0 <= k <= len(nums)

Enumerating all O(n²) subarrays and counting their zeros is ~10^10 steps at the top end; the expected solution is one O(n) pass.

Think about it first

TL;DR

Variable-size sliding window keeping at most k zeros inside — O(n) time, O(1) space.

Approach 1 — Brute force

For every start index, extend right until the (k+1)-th zero appears.

def longestOnes(nums: list[int], k: int) -> int:
    n = len(nums)
    best = 0
    for i in range(n):
        zeros = 0
        for j in range(i, n):
            if nums[j] == 0:
                zeros += 1
            if zeros > k:
                break
            best = max(best, j - i + 1)
    return best

Complexity: O(n²) time, O(1) space. At n = 10^5, up to ~5 * 10^9 iterations — the constraints rule it out.

Approach 2 — Sliding window

The problem is “longest window with at most k zeros,” and that validity is monotone: shrinking a valid window keeps it valid, extending an invalid one keeps it invalid. So for each right there is a frontier left that only moves forward. Two pointers each cross the array once, with a single integer (the zero count) summarizing the window.

def longestOnes(nums: list[int], k: int) -> int:
    left = 0
    zeros = 0
    best = 0
    for right, x in enumerate(nums):
        if x == 0:
            zeros += 1
        while zeros > k:                 # too many zeros: shrink from the left
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Walkthrough on nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2:

Answer: 6 (indices 5–10 after flipping the zeros at 5 and 10).

Complexity: left and right each advance at most n times → O(n) time; O(1) space.

Approach 3 — Non-shrinking (rigid slide) variant

Since only the maximum window length matters, the window never needs to get smaller. When the incoming element breaks validity, slide the whole window right by one instead of shrinking it in a loop; the window size becomes a high-water mark.

def longestOnes(nums: list[int], k: int) -> int:
    left = 0
    zeros = 0
    for right, x in enumerate(nums):
        if x == 0:
            zeros += 1
        if zeros > k:                    # slide rigidly: window size never decreases
            if nums[left] == 0:
                zeros -= 1
            left += 1
    return len(nums) - left

Complexity: O(n) time, O(1) space — same asymptotics as Approach 2, marginally fewer operations (no inner loop), but the “window size = answer so far” invariant is subtler to defend in an interview.

Common pitfalls

• Counting the window before restoring validity. In Approach 2, update best only after the while loop — an oversized window with k+1 zeros must never be measured.
• Decrementing zeros unconditionally when moving left. Only departing zeros reduce the count; dropping a 1 changes nothing.
• k = 0 is not a special case. The algorithm reduces to “longest run of 1s” on its own, so no branching is needed.
• Shrink with while, slide with if. Approach 2 needs while to remove every excess zero; Approach 3 uses if to move left exactly once per step. Here at most one zero enters per step, so a single shrink always suffices, but while is the safe default when the entering element could add more than one to the count.

Pattern takeaway

“Flip at most k” problems are usually sliding windows. Translate the operation budget into a window-validity predicate (“at most k bad elements inside”), confirm that predicate is monotone under shrinking, and the standard grow-right/shrink-left loop with an O(1) counter gives a linear algorithm. The key step is converting “edits allowed” into “defects tolerated.”