Leetcode 1004. Max Consecutive Ones III

Let's understand what we're being asked to do. We have a binary array (containing only 0s and 1s) like [1,1,1,0,0,0,1,1,1,1,0], and we can flip at most k zeros to ones. We need to find the maximum length of a contiguous subarray that can be made all 1s.

Tracing through with k=2: If we flip the zeros at indices 3 and 4, we get [1,1,1,1,1,0,1,1,1,1,0] - that's 5 consecutive ones. But if we flip zeros at indices 9 and 10, we get [1,1,1,0,0,0,1,1,1,1,1] - that's also 5 consecutive ones. Can we do better? If we flip zeros at indices 3 and 5, we get [1,1,1,1,0,1,1,1,1,1,0] - but that's not all consecutive because of the zero at index 4.

Important constraint: We can flip at most k zeros, not exactly k. This means we're looking for the longest window that contains at most k zeros.

Edge cases to consider: What if k=0 (can't flip any zeros)? What if the array has no zeros at all? What if k is greater than the number of zeros in the array?

The brute force approach checks every possible subarray: for each starting position, expand to every possible ending position and count the zeros in that window. If the zero count is at most k, calculate the window length and track the maximum. This requires nested loops to generate all subarrays and an inner loop or counter to count zeros in each window.

def max_ones_with_k_flips(nums, k):
    """
    Brute force: Check every possible subarray.
    For each subarray, count zeros. If zeros <= k, track max length.
    """
    n = len(nums)
    max_length = 0
    
    # Try every starting position
    for start in range(n):
        zero_count = 0
        
        # Try every ending position from start
        for end in range(start, n):
            # Count zeros in current window
            if nums[end] == 0:
                zero_count += 1
            
            # If we can flip all zeros in this window
            if zero_count <= k:
                current_length = end - start + 1
                max_length = max(max_length, current_length)
    
    return max_length

Instead of thinking about "flipping zeros to ones", reframe the problem: find the longest contiguous subarray containing at most k zeros.

If a subarray has at most k zeros, we can flip all those zeros to make the entire subarray all 1s. The length of that subarray is our answer.

This reframing transforms the problem from "what should I flip?" to "what's the longest valid window?"

We can use a window that expands and contracts: expand the window to include more elements, and when we exceed k zeros, contract from the left until we're valid again. This gives us O(n) time instead of checking all possible subarrays.

Imagine you're reading the array from left to right with a rubber band. You stretch the rubber band to the right as far as possible while keeping at most k zeros inside.

When you encounter too many zeros (more than k), you release the left end of the rubber band until you're back to at most k zeros. The longest stretch of the rubber band you achieve is your answer.

The optimal approach uses a sliding window with two pointers (left and right). Expand the window by moving right and count zeros encountered. When the zero count exceeds k, contract the window from the left until we have at most k zeros again. Track the maximum window size throughout this process. This ensures each element is visited at most twice (once by right pointer, once by left pointer), achieving linear time complexity.

def max_ones_with_k_flips(nums, k):
    """
    Find the maximum length of a contiguous subarray that can be made all 1s
    by flipping at most k zeros using sliding window technique.
    """
    left = 0
    zero_count = 0
    max_length = 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
        
        current_length = right - left + 1
        max_length = max(max_length, current_length)
    
    return max_length

• Sliding window for constraint satisfaction: When a problem asks for the longest/shortest subarray satisfying a constraint (at most k of something), use the two-pointer sliding window pattern - expand right to grow the window, contract left when constraint is violated, tracking the maximum valid window size throughout.
• Window validity with counter tracking: Maintain a zero count (or constraint violation count) as you slide - increment when adding problematic elements, decrement when removing them. This O(1) validity check is far more efficient than rescanning the window each time.
• Shrink-until-valid pattern: When the window becomes invalid (zeros > k), use a while loop to shrink from the left until valid again, not just a single step - this ensures you always maintain the constraint and don't miss the optimal window.
• Result calculation timing: Calculate `maxLength = max(maxLength, right - left + 1)` after ensuring the window is valid, not before shrinking - a common mistake is recording invalid window sizes, which produces incorrect results.
• O(n) two-pointer guarantee: Each element is visited at most twice (once by right pointer, once by left pointer), guaranteeing O(n) time complexity even though there's a nested while loop - the left pointer never resets, making this linear, not quadratic.
• Constraint transformation insight: Reframe "flip at most k zeros" as "find longest subarray with at most k zeros" - this problem transformation reveals the sliding window pattern and applies to similar constraint problems (at most k distinct characters, at most k replacements, etc.).