Max Consecutive Ones II

Problem Description

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

Naive Solution

The brute-force approach involves iterating through each element of the array. For each element, we assume it's the zero we're flipping and then calculate the consecutive ones. We keep track of the maximum consecutive ones seen so far.

1. Iterate through the array with index i.
2. For each i, flip the bit at that index temporarily.
3. Calculate the maximum consecutive ones in the modified array.
4. Update the overall maximum.
5. Revert the flip.

def max_consecutive_ones_brute_force(nums):
    max_ones = 0
    for i in range(len(nums)):
        original_value = nums[i]
        nums[i] = 1  # Flip the bit
        current_max = 0
        count = 0
        for j in range(len(nums)):
            if nums[j] == 1:
                count += 1
                current_max = max(current_max, count)
            else:
                count = 0
        max_ones = max(max_ones, current_max)
        nums[i] = original_value  # Revert the flip
    
    count = 0
    for j in range(len(nums)):
        if nums[j] == 1:
            count += 1
            max_ones = max(max_ones, count)
        else:
            count = 0

    return max_ones

Time Complexity: O(n^2), where n is the length of the array, due to nested loops.

Space Complexity: O(1), as it uses a constant amount of extra space.

Optimal Solution

A more efficient solution utilizes the sliding window technique. We maintain a window that contains at most one zero. We expand the window to the right and, if we encounter a second zero, shrink the window from the left until we only have one zero.

1. Initialize left and right pointers to 0.
2. Initialize a zero_count to 0.
3. Iterate through the array using the right pointer.
4. If nums[right] is 0, increment zero_count.
5. While zero_count is greater than 1, move the left pointer to the right. If nums[left] is 0, decrement zero_count.
6. Update the maximum length with right - left + 1.

def max_consecutive_ones(nums):
    left = 0
    zero_count = 0
    max_length = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        while zero_count > 1:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        max_length = max(max_length, right - left + 1)

    return max_length

Time Complexity: O(n), where n is the length of the array, as each element is visited at most twice.

Space Complexity: O(1), as it uses a constant amount of extra space.

Edge Cases

• Empty array: Should return 0.
• Array with all ones: Should return the length of the array.
• Array with all zeros: Should return 1.
• Array with a single zero: Should return the length of the array.

Code with Edge Cases

def max_consecutive_ones_edge_cases(nums):
    if not nums:
        return 0

    left = 0
    zero_count = 0
    max_length = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        while zero_count > 1:
            if nums[left] == 0:
                zero_count -= 1
            left += 1

        max_length = max(max_length, right - left + 1)

    return max_length