Max Consecutive Ones III: Sliding Window with Flips

You are given a binary array nums and an integer k. You can flip at most k zeros to ones. Return the maximum number of consecutive 1s in the array after performing at most k flips. This is LeetCode 1004: Max Consecutive Ones III.

For example, given nums = [1,1,1,0,0,0,1,1,1,1,0,0] and k = 2, the answer is 6. You can flip two of the zeros to create a window of six consecutive ones.

Why this problem matters

Sliding window problems are some of the most common questions in technical interviews, and Max Consecutive Ones III is one of the best for building that skill. It teaches you how to maintain a flexible window that grows and shrinks based on a constraint (the number of flipped zeros). The same pattern appears in problems like "Longest Substring Without Repeating Characters," "Longest Repeating Character Replacement," and "Minimum Window Substring."

Once you internalize this version, you can adapt it to any problem where you need to find the longest subarray satisfying some condition that you can track with a counter.

The key insight

You do not actually flip any zeros. Instead, you maintain a sliding window and count how many zeros are inside it. As long as the zero count is <= k, the window is valid because you could flip those zeros. When the count exceeds k, you shrink the window from the left until the count drops back to k.

The problem transforms from "flip at most k zeros" into "find the longest subarray containing at most k zeros." That reframing makes the sliding window approach natural.

The algorithm:

1. Initialize two pointers, left and right, both at 0. Track zero_count and best.
2. Expand right one step at a time. If nums[right] is 0, increment zero_count.
3. While zero_count exceeds k, shrink from the left. If nums[left] is 0, decrement zero_count. Move left forward.
4. Update best with the current window size (right - left + 1).
5. After right passes the end, return best.

The solution

def longest_ones(nums, k):
    left = 0
    zero_count = 0
    best = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

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

        best = max(best, right - left + 1)

    return best

The outer for loop advances right across the entire array. Every time we include a new element, we check if it is a zero and update the count. The inner while loop fires only when we have too many zeros in the window. It moves left forward, undoing the effect of any zero that leaves the window, until the constraint is satisfied again. After each adjustment, we record the window size if it is the new maximum.

The key detail is that left never moves backward. Both pointers sweep from left to right across the array, so the total work is linear.

Visual walkthrough

Let's trace through nums = [1,1,1,0,0,0,1,1,1,1,0,0] with k = 2. Watch how the window expands when zeros are within budget and contracts when the count exceeds k. Green cells are 1s inside the window, yellow cells are flipped zeros, and red cells are zeros that have not been flipped.

Notice how the window reaches its maximum size of 6 at step 5, spanning indices 4 through 9. After that, every new zero forces the left pointer to advance past an old zero, keeping the window size steady at 6. The best answer never decreases.

Complexity analysis

Time is O(n) where n is the length of the array. Although there is a while loop inside a for loop, the left pointer only moves forward and never revisits an element. Each element is visited at most twice (once by right, once by left), so the total number of operations is at most 2n.

Space is O(1). We only use a few integer variables (left, zero_count, best). No extra data structures are needed.

The building blocks

1. Expanding the window

The core of any sliding window is the expansion step. You move the right pointer forward and update your tracking variable:

for right in range(len(nums)):
    if nums[right] == 0:
        zero_count += 1

This is the same in every sliding window problem. The only thing that changes is what you track. Here it is zero count. In "Longest Substring Without Repeating Characters" it is a set of characters. In "Minimum Window Substring" it is a frequency map. The expansion logic is always one line of bookkeeping after advancing right.

2. Shrinking to restore the constraint

When the window violates its constraint, you shrink from the left until it is valid again:

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

The while loop ensures you keep shrinking until the constraint holds. The undo logic inside mirrors the expansion logic: if adding a zero incremented the count, removing a zero decrements it. This symmetry between expanding and shrinking is the pattern you want to internalize. Once you can write both sides without thinking, any sliding window problem becomes a matter of plugging in the right constraint.

Edge cases

Before submitting, think through these scenarios:

• All ones: nums = [1,1,1,1], any k. Zero count never increases. The window spans the whole array. Return len(nums).
• All zeros, k equals length: nums = [0,0,0], k = 3. You flip every zero. Return len(nums).
• All zeros, k equals 0: nums = [0,0,0], k = 0. The window can never include a zero. Return 0.
• k equals 0: The problem reduces to "Max Consecutive Ones" (LeetCode 485). No flips allowed, just find the longest run of 1s.
• k larger than the number of zeros: You can flip every zero. Return len(nums).
• Single element: nums = [0], k = 1 returns 1. nums = [1], k = 0 returns 1.

From understanding to recall

You now understand the sliding window with a zero-flip budget. The logic is clean: expand right, track zeros, shrink left when over budget, record the best. But under interview pressure, small details trip people up. Do you use while or if for the shrink? Do you update best inside or outside the while? Do you check zero_count > k or zero_count >= k?

These are not conceptual mistakes. They are recall gaps. Spaced repetition is how you close them. You practice writing the expand-and-shrink loop from memory, first after a day, then after three days, then after a week. After a few rounds, the pattern flows out automatically. You see "longest subarray with at most k of something" and you write the solution without pausing to think about the details.

Related posts

• Longest Substring Without Repeating Characters - Classic sliding window for unique characters
• Minimum Window Substring - Sliding window with character frequency tracking
• Max Consecutive Ones - The simpler version without flips

CodeBricks breaks Max Consecutive Ones III into its expand-window and shrink-window building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sliding window problem shows up in your interview, you do not think about it. You just write it.