Max Consecutive Ones III — InterviewPrepKit

Solving tips

Restate 'flip at most k zeros' as 'longest window containing at most k zeros', the classic operation-budget-to-window translation.
Maintain a running zero count; grow right unconditionally and shrink left while zeros > k, tracking the max window size.
Validity (at most k zeros) is monotone under shrinking, so both pointers move forward only, giving O(n) time and O(1) space.
Common pitfall: record best only after restoring validity, and decrement the zero count only when the element leaving left is actually a 0.

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

Hint 1

Forget flipping — restate the goal: longest window containing at most k zeros. Which single number summarizes a window for this test?

Hint 2

If a window has at most k zeros, so does any window inside it; if it has more, so does any window around it. Monotone validity means two forward-only pointers suffice.

Hint 3

Keep a running count of zeros in the window. Advance right each step (count the entering zero); while the count exceeds k, advance left (uncount the leaving zero). Track the largest window ever valid.

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.

class Solution:
    def longestOnes(self, 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 insight: 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. Hence for each right there is a frontier left that only moves forward — two pointers, each crossing the array once, with a single integer (the zero count) summarizing the window.

class Solution:
    def longestOnes(self, 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:

right	x	zeros (before shrink)	shrink?	left	window len	best
0–2	1,1,1	0	no	0	3	3
3	0	1	no	0	4	4
4	0	2	no	0	5	5
5	0	3	yes → drop idx 0–3 (last is a zero)	4	2	5
6	1	2	no	4	3	5
7	1	2	no	4	4	5
8	1	2	no	4	5	5
9	1	2	no	4	6	6
10	0	3	yes → drop idx 4 (a zero)	5	6	6

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

The insight: 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.

class Solution:
    def longestOnes(self, 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; resist the urge to branch.
Shrink with while, slide with if — mixing them up either lets the window stay invalid (using if where multiple shrinks are needed… here at most one zero enters per step, so if happens to suffice, but while is the safe default) or turns the rigid variant back into a shrinking one.

Pattern takeaway

“Flip at most k” problems are usually windows in disguise: translate the operation budget into a window-validity predicate (“at most k bad elements inside”), check that the predicate is monotone under shrinking, and the standard grow-right/shrink-left loop with an O(1) summary counter gives a linear algorithm. The transformation — from edits allowed to defects tolerated — is the step to remember.