Max Consecutive Ones II

How it works

Instead of restarting from every position, we can use a sliding window that grows and shrinks dynamically. The key insight is that we only need to shrink the window when we have more than one zero inside it. By maintaining a count of zeros in the current window, we expand by moving the right pointer and contract by moving the left pointer whenever the window becomes invalid. This way, each element is visited at most twice, making the solution linear.

Steps

1. Initialize two pointers left and right at 0, along with numZeroes to track zeros in the window.
2. Expand the window by moving right:
   • If the element at right is 0, increment numZeroes.
3. While numZeroes equals 2 (window is invalid):
   • If the element at left is 0, decrement numZeroes.
   • Move left forward to shrink the window.
4. Update longestSequence with the current window size (right - left + 1).
5. Continue until right reaches the end, then return longestSequence.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) constant space used

Where n is the length of the input array nums.

Things to watch for

Off-by-One Errors in Window Size Calculation

When calculating the window size, remember that for indices left and right, the window size is right - left + 1, not right - left. Forgetting the +1 results in consistently underreporting the maximum consecutive ones by one.

Incorrectly Handling the Zero Count Threshold

The window becomes invalid when numZeroes reaches 2 (since we can only flip one zero). A common mistake is using numZeroes > 1 in some places and numZeroes == 2 in others, leading to inconsistent behavior. Be consistent with your threshold check and ensure you shrink the window only when you have exceeded the allowed number of zeros.

Not Updating the Maximum Before Shrinking

Make sure to update the longest sequence answer at the right time. If you shrink the window first and then try to update the maximum, you might miss the optimal window size. In the sliding window approach, update the result after ensuring the window is valid, not before handling the invalid case.

from typing import List

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        longest_sequence = 0
        left, right = 0, 0
        num_zeroes = 0

        while right < len(nums):   # While our window is in bounds
            if nums[right] == 0:    # Increase num_zeroes if the rightmost element is 0
                num_zeroes += 1

            while num_zeroes == 2:   # If our window is invalid, contract our window
                if nums[left] == 0:
                    num_zeroes -= 1
                left += 1

            longest_sequence = max(longest_sequence, right - left + 1)   # Update our longest sequence answer
            right += 1   # Expand our window

        return longest_sequence

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int longestSequence = 0;
        int left = 0;
        int right = 0;
        int numZeroes = 0;

        // While our window is in bounds
        while (right < nums.size()) {

            // Increase numZeroes if the rightmost element is 0
            if (nums[right] == 0) {
                numZeroes++;
            }

            //If our window is invalid, contract our window
            while (numZeroes == 2) {
                if (nums[left] == 0) {
                    numZeroes--;
                }
                left++;
            }

            // Update our longest sequence answer
            longestSequence = max(longestSequence, right - left + 1);

            // Expand our window
            right++;
        }

        return longestSequence;
    }
};