Leetcode 487. Max Consecutive Ones II

Problem

You are given a binary array containing only 0s and 1s. Your task is to find the maximum number of consecutive 1s you can achieve in the array if you are allowed to flip at most one 0 to a 1.

In other words, you want to find the longest contiguous subarray that can be made to contain all 1s by changing at most a single 0 to a 1.

Requirements

1. Return the length of the longest sequence of consecutive 1s possible
2. You may flip at most one 0 to a 1
3. The solution should handle arrays of any length
4. The array contains only 0s and 1s

Constraints

• 1 ≤ nums.length ≤ 100,000
• nums[i] is either 0 or 1
• Aim for O(n) time complexity and O(1) space complexity

Examples

Example 1:

Input: nums = [1, 0, 1, 1, 0] Output: 4 Explanation: Flip the 0 at index 1 to get [1, 1, 1, 1, 0]. The longest sequence of 1s is now 4.

Example 2:

Input: nums = [1, 1, 1, 1] Output: 4 Explanation: All elements are already 1. No flip needed.

Example 3:

Input: nums = [0, 0, 0] Output: 1 Explanation: We can flip any one 0 to get a sequence of length 1.

Hint 1: Sliding Window

Hint 2: Two Pointers Use two pointers (left and right) to define your window. When you encounter more than one 0 in your window, shrink the window from the left until you have at most one 0 again.

Hint 3: Count Zeros Keep a counter for the number of zeros in your current window. When this count exceeds 1, move your left pointer forward until the count drops back to 1 or less.

Full Solution ` def findMaxConsecutiveOnes(nums): # Two pointer approach with sliding window left = 0 max_length = 0 zero_count = 0

# Expand window with right pointer
for right in range(len(nums)):
    # If we encounter a 0, increment our zero counter
    if nums[right] == 0:
        zero_count += 1
    
    # If we have more than one 0, shrink window from left
    while zero_count > 1:
        if nums[left] == 0:
            zero_count -= 1
        left += 1
    
    # Update max length with current window size
    max_length = max(max_length, right - left + 1)

return max_length

`

Explanation:

The solution uses a sliding window technique with two pointers:

1. Initialize variables: We track the left boundary of our window, max_length for the result, and zero_count to count zeros in our current window.
2. Expand the window: The right pointer iterates through the array, expanding our window. When we encounter a 0, we increment zero_count.
3. Shrink when needed: If zero_count exceeds 1 (meaning we have more than one 0 in our window), we shrink the window from the left until we have at most one 0 again.
4. Track maximum: After each expansion, we update max_length with the size of the current window, which represents a valid sequence that can be made all 1s by flipping at most one 0.

Time Complexity: O(n) where n is the length of the array. Each element is visited at most twice (once by right pointer, once by left pointer).

Space Complexity: O(1) as we only use a constant amount of extra space for our pointers and counters.