Max Consecutive Ones Ii - Leetcode Solution

Problem Statement:

Given a binary array, find the maximum number of consecutive 1s in this array with at most one 0.

Example:

Input: [1,0,1,1,0] Output: 4 Explanation: Flip the first zero will get the maximum number of consecutive 1s. After flipping, the maximum number of consecutive 1s is 4.

Solution:

One brute force way to solve this problem is to check every possible scenario (flipping each 0) and find the maximum number of consecutive 1s. However, this will be highly inefficient with a time complexity of O(n^2).

A more optimized solution would be to keep track of the length of the current consecutive ones sequence and the length of the previous consecutive ones sequence. Whenever a 0 is encountered, the previous length is updated to the current length, and the current length is reset to 0. If another 0 is encountered, the same process repeats.

The maximum length seen so far can be updated whenever a 0 is encountered by adding the current length and the previous length.

Let's see the implementation of the above approach in Python:

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        max_length = 0
        curr_length = 0
        prev_length = 0
        
        for num in nums:
            if num == 1:
                curr_length += 1
            else:
                prev_length = curr_length
                curr_length = 0
            max_length = max(max_length, curr_length + prev_length + 1)
        
        return max_length

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input array.

Space Complexity:

The space complexity of this solution is O(1) since we are only using constant extra space to store the lengths of the current and previous consecutive ones sequences.

1