LeetCode Solutions Blog

Max Consecutive Ones II

Number: 487

Difficulty: Medium

Paid? Yes

Problem Description

Given a binary array nums, return the maximum number of consecutive 1's in the array if you can flip at most one 0.

Key Insights

Utilize a sliding window to maintain the current segment.
The window can contain at most one 0.
Expand the window with the right pointer and contract it with the left pointer when the constraint is violated.
The maximum window size observed during this process is the desired result.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array.
Space Complexity: O(1).

Solution

We use a sliding window approach to efficiently find the longest contiguous subarray that contains at most one 0. Two pointers (left and right) define the window. As we iterate with the right pointer, counting zeros in the window, we adjust the left pointer when the count of zeros exceeds one. The length of the valid window gives us the number of consecutive 1's (considering one flipped 0), and we update the maximum length accordingly.

Code Solutions

# Function to find the maximum consecutive ones with at most one zero flip
def findMaxConsecutiveOnes(nums):
    max_length = 0  # Tracks the maximum length of the window
    left = 0  # Left pointer for the sliding window
    zero_count = 0  # Counter for zeros in the current window

    # Iterate with right pointer over the entire array
    for right in range(len(nums)):
        # If current element is zero, increase the zero_count
        if nums[right] == 0:
            zero_count += 1

        # If window invalid (more than one zero), shrink from left
        while zero_count > 1:
            if nums[left] == 0:
                zero_count -= 1
            left += 1
        
        # Update max_length if current window is larger
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage:
# nums = [1,0,1,1,0]
# print(findMaxConsecutiveOnes(nums))  # Expected output: 4