1. Brute Force

Intuition

The most straightforward approach is to check every possible starting position and see how far we can extend while flipping at most k zeros. For each starting index, we move forward and count zeros. Once the count exceeds k, we stop and record the window length. This method explores all contiguous subarrays but performs redundant work by rescanning overlapping regions.

Algorithm

1. Initialize res to store the maximum length found.
2. For each starting index l, set a zero counter cnt to 0 and expand with pointer r:
   • If the current element is 0 and cnt already equals k, stop expanding.
   • Otherwise, if the element is 0, increment cnt.
   • Move r forward.
3. After the inner loop, update res with r - l.
4. Return res after checking all starting positions.

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        res = 0
        for l in range(len(nums)):
            cnt, r = 0, l
            while r < len(nums):
                if nums[r] == 0:
                    if cnt == k:
                        break
                    cnt += 1
                r += 1
            res = max(res, r - l)
        return res

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(1)$

---

2. Binary Search + Prefix Sum

Intuition

We can precompute a prefix sum array that counts zeros up to each index. For any subarray from l to r, the number of zeros is simply prefix[r + 1] - prefix[l]. This allows us to quickly check if a window is valid (contains at most k zeros). For each starting position, we binary search for the farthest ending position where the zero count stays within the limit. This avoids the linear scan of the brute force approach.

Algorithm

1. Build a prefix sum array where prefix[i] stores the count of zeros in nums[0..i-1].
2. For each starting index l, binary search for the largest r such that prefix[r + 1] - prefix[l] <= k.
3. Update res with r - l (the window length).
4. Return res after processing all starting positions.

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        prefix = [0]
        for num in nums:
            prefix.append(prefix[-1] + (1 if num == 0 else 0))
        
        res = 0
        for l in range(len(nums)):
            low, high = l, len(nums)
            while low < high:
                mid = (low + high) // 2
                if prefix[mid + 1] - prefix[l] <= k:
                    low = mid + 1
                else:
                    high = mid
            res = max(res, low - l)
        return res

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

3. Sliding Window

Intuition

A sliding window provides the optimal approach. We maintain a window that can contain at most k zeros. As we expand the right boundary, we decrement k for each zero encountered. When k goes negative, the window has too many zeros, so we shrink from the left until the window is valid again. The maximum window size seen during this process is our answer. Each element is processed at most twice, yielding linear time complexity.

Algorithm

1. Initialize l (left pointer) and res (result) to 0.
2. Iterate through the array with r (right pointer):
   • If nums[r] is 0, decrement k.
   • While k < 0 (window is invalid):
     • If nums[l] is 0, increment k (restore the flip allowance).
     • Move l forward.
   • Update res with r - l + 1.
3. Return res.

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = res = 0
        for r in range(len(nums)):
            k -= (1 if nums[r] == 0 else 0)
            while k < 0:
                k += (1 if nums[l] == 0 else 0)
                l += 1
            res = max(res, r - l + 1)
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

---

Common Pitfalls

Modifying k Without Restoring It

When using k directly as a counter (decrementing when encountering zeros), remember that this mutates the input parameter. If you need to use k again later or if the problem requires preserving it, use a separate variable. Additionally, when shrinking the window, you must restore k by incrementing it when a zero leaves the window.

Incorrect Window Shrinking Condition

The window should shrink when k < 0, meaning we have flipped more zeros than allowed. A common mistake is using k == 0 as the shrinking condition, which prevents the window from ever containing k zeros. The window is valid as long as k >= 0; only shrink when it becomes negative.

Forgetting to Handle Edge Cases

When k equals or exceeds the number of zeros in the array, the answer is simply the length of the entire array. While the sliding window approach handles this naturally, the brute force approach might have issues if not carefully implemented. Also, handle the case when the array is empty or contains only ones.