Max Consecutive Ones III

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

from typing import List

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

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int l = 0, res = 0;
        for (int r = 0; r < nums.size(); ++r) {
            k -= (nums[r] == 0 ? 1 : 0);
            while (k < 0) {
                k += (nums[l] == 0 ? 1 : 0);
                ++l;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};