Generated by Codex with GPT-5

Quick facts

What the problem is really asking

This problem sounds like a bit-flipping question, but the useful reframe is simpler:

find the longest contiguous subarray that contains at most k zeroes.

Why does that reframe work? Because every zero inside the chosen window would need to be flipped to make the whole window all ones. If the window contains:

  • 0 zeroes, it already works
  • 1 zero, it costs one flip
  • 2 zeroes, it costs two flips

So the real constraint is not “how many ones can be produced globally?” It is:

how long can a window stay while using at most k zero-flips?

That is a classic sliding-window setup.

The first correct idea

A perfectly reasonable first thought is brute force:

  1. Pick every possible left boundary.
  2. Expand the right boundary.
  3. Count how many zeroes are inside.
  4. Stop when the zero count exceeds k.

That approach is correct, and it helps expose the structure of the problem, but it repeats a lot of work. Adjacent windows overlap heavily, so restarting the scan from scratch for each left boundary leads to O(n^2) behavior in the worst case.

Once that overlap becomes obvious, the next question is:

“Can the current window be repaired instead of rebuilt?”

That is the step that leads to the optimal solution.

Why sliding window is optimal

Suppose the current window is valid, which means it contains at most k zeroes. If the next element on the right is added:

  • if it is 1, the window is still valid
  • if it is 0, the window might become invalid

Now the key observation:

if the window has too many zeroes, moving the right boundary farther right will never fix it. The extra zeroes are still inside the window. The only way to restore validity is to move the left boundary rightward until enough zeroes leave the window.

That gives the full algorithm:

  1. Expand the right pointer one step at a time.
  2. Track how many zeroes are inside the current window.
  3. Whenever the zero count exceeds k, move the left pointer right until the window is valid again.
  4. After each repair, record the best window length seen so far.

The reason this is optimal is that each index enters the window once and leaves the window once. There is no backtracking. That makes the whole scan linear.

A concrete example

Take:

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

As the right pointer expands, the window stays valid until it contains three zeroes. At that moment, the flip budget has been exceeded, so the left pointer starts moving right until one of those zeroes falls out of the window.

The important idea is that the algorithm never throws away more of the window than necessary. It keeps the longest possible valid suffix ending at the current right pointer. Across the full scan, the best such window has length 6.

That is exactly the answer LeetCode expects.

How to derive this in an interview

A clean interview explanation usually goes like this:

  1. Rephrase the problem as “longest subarray with at most k zeroes.”
  2. Identify the window validity rule: only the zero count matters.
  3. Notice that once a window is invalid, shrinking from the left is the only repair move.
  4. Maintain that invariant with two pointers and a running zero count.

That line of reasoning is strong because it shows understanding instead of memorizing “use sliding window here.”

Python solution

from typing import List


def longest_window_with_at_most_k_zero_flips(
    binary_values: List[int],
    max_zero_flips: int,
) -> int:
    """
    Return the length of the longest contiguous subarray that can be turned
    into all ones by flipping at most `max_zero_flips` zeroes.
    """
    left_index = 0
    zero_count_in_window = 0
    best_window_length = 0

    for right_index, value in enumerate(binary_values):
        if value == 0:
            zero_count_in_window += 1

        # If the current window needs too many flips, move the left edge
        # until the window becomes valid again.
        while zero_count_in_window > max_zero_flips:
            if binary_values[left_index] == 0:
                zero_count_in_window -= 1
            left_index += 1

        current_window_length = right_index - left_index + 1
        if current_window_length > best_window_length:
            best_window_length = current_window_length

    return best_window_length


class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        return longest_window_with_at_most_k_zero_flips(
            binary_values=nums,
            max_zero_flips=k,
        )

Why this works

The invariant is simple but powerful:

after the inner while loop finishes, the current window always contains at most k zeroes.

That means the window is always a valid candidate answer. It is also the longest valid window ending at the current right_index, because the left pointer moves only when it must. Any earlier left boundary would leave too many zeroes in the window.

Taking the maximum over all right boundaries therefore finds the global optimum.

The time complexity is O(n) because each pointer moves from left to right at most once. The extra space is O(1) because the algorithm stores only a few integers.

Interview follow-ups

Can you return the actual subarray, not just its length?

Yes. Keep two extra variables for the best window boundaries, such as best_left_index and best_right_index, and update them whenever a longer valid window is found. Nothing about the sliding-window logic changes. The same invariant still holds, and the complexity stays O(n) time with O(1) extra space. The only difference is a small amount of bookkeeping so the final answer can include indices or the subarray itself.

There is a valid alternative solution using a prefix sum of zero counts. Once that prefix array exists, the number of zeroes in any window can be computed in O(1). From there, there are two common O(n log n) directions. One is to binary search the farthest valid right boundary for each fixed left boundary. The other is to binary search the answer length itself and check whether any window of that length uses at most k flips. Those methods are correct because the number of zeroes in a fixed-start window grows monotonically as the right boundary moves right. They are good to know, but the sliding-window solution is still the best practical answer here because it is simpler and improves the runtime to O(n).

What changes if the input arrives as a stream instead of a full array?

If the full array is not stored, the usual left_index approach becomes awkward because shrinking the window requires knowing which value is leaving on the left. A common streaming-friendly fix is to store the positions of zeroes in a queue. Each time a new zero arrives, push its index. If the queue grows beyond k, pop the oldest zero position and move the left boundary to one index after it. That version still runs in O(n) time, but the extra space becomes O(k) instead of O(1). The tradeoff is worth it when the data truly arrives online and old values are no longer directly accessible.

How does this generalize to other interview problems?

This pattern shows up whenever the question asks for the longest contiguous segment that can tolerate at most k “bad” items. Sometimes the bad items are zeroes, sometimes they are characters that need replacement, and sometimes they are values that violate a threshold. The reusable mental model is: maintain a window, track the cost of the current window, and shrink from the left whenever the budget is exceeded. What changes from problem to problem is only the definition of the window cost and how that cost is updated when elements enter or leave.

Practical takeaway

The fastest way to recognize this problem is to ignore the flipping story and focus on the budget:

the chosen window may contain at most k zeroes.

Once the problem is stated that way, the optimal solution becomes a direct sliding-window scan with a zero counter.