Max Consecutive Ones III (LeetCode 1004)

The problem

You get a binary array nums (only 0s and 1s) and an integer k. You may flip at most k zeros to ones. Return the length of the longest run of consecutive 1s you can end up with.

Input:  nums = [1, 0, 0, 1, 1, 0, 1], k = 1
Output: 4

Flip the zero at index 5: indices 3 to 6 become 1, 1, 1, 1, a run of 4.

How to think about it

Start with brute force. Try every subarray, count its zeros, and keep the longest with at most k zeros: O(n²) even with running counts. You could also try every set of k zeros to flip, which is far worse.

Reframe the flips. You never need to decide which zeros to flip up front. A subarray can be turned into all 1s exactly when it contains at most k zeros: flip those and you’re done. So the problem becomes: find the longest subarray with at most k zeros.

The key insight: that condition suits a variable window. Grow the window to the right one element at a time, counting zeros. If the count goes over k, the window is invalid, and since any bigger window containing it is also invalid, the fix is to move the left edge right until a zero falls out. Every valid window you see is a candidate for the answer.

Which pattern is this? A variable-size sliding window with a counter. The tell is “longest subarray with at most k bad elements”.

Approach

1. Keep start = 0, zeros = 0, best = 0.
2. For each i, if nums[i] is 0, increase zeros.
3. While zeros > k, move start right, decreasing zeros when the element leaving is a 0.
4. Update best = max(best, i - start + 1).
5. Return best.

Solution

def longest_ones(nums, k):
    start = 0; zeros = 0; best = 0
    for i, x in enumerate(nums):
        if x == 0: zeros += 1
        while zeros > k:                           # too many flips needed
            if nums[start] == 0: zeros -= 1
            start += 1
        best = max(best, i - start + 1)
    return best
# longest_ones([1,1,1,0,0,0,1,1,1,1,0], 2) -> 6

Dry run

On nums = [1, 0, 0, 1, 1, 0, 1], k = 1:

(At i = 3 the window is indices 2 to 3, length 2.) The answer is 4.

Complexity

• Time: O(n). i and start each move right at most n times.
• Space: O(1). Three integers.

Edge cases and pitfalls

• k = 0: the answer is the longest existing run of 1s.
• k at least the number of zeros: the whole array is valid, so return n.
• All zeros with k > 0 returns min(k, n).
• Off-by-one on length. The window nums[start..i] has length i - start + 1.
• Greedy “flip the next zero” without a window gets messy fast. Thinking in terms of “at most k zeros in the window” keeps it simple.

Related problems

• Longest Subarray of 1’s After Deleting One Element (LeetCode 1493): the same window with k = 1, minus the deleted slot.
• Longest Repeating Character Replacement (LeetCode 424): the multi-letter version of a replacement budget.
• Minimum Size Subarray Sum (LeetCode 209): the “shortest window” twin of this “longest window” template.