Jobs

Interviews

Discussions

Max Consecutive Ones II

Medium

Asked by:

15 views

Topics:

ArraysSliding WindowsTwo Pointers

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

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will result in 1, 1, 1, 1, 0. The maximum number of consecutive 1s is 4.

Example 2:

Input: nums = [1,0,1,1,0,1,1]
Output: 4
Explanation: Flip the first zero will result in 1, 1, 1, 1, 0, 1, 1. The maximum number of consecutive 1s is 4.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is either 0 or 1.

Try coding it in LeetCode

Max Consecutive Ones II

Medium

Asked by:

15 views

Topics:

ArraysSliding WindowsTwo Pointers

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

Example 1:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will result in 1, 1, 1, 1, 0. The maximum number of consecutive 1s is 4.

Example 2:

Input: nums = [1,0,1,1,0,1,1]
Output: 4
Explanation: Flip the first zero will result in 1, 1, 1, 1, 0, 1, 1. The maximum number of consecutive 1s is 4.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is either 0 or 1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the input array is null or empty?
Can the input array contain values other than 0 and 1?
If there are multiple subarrays with the same maximum number of consecutive ones after flipping at most one 0, which one should I return (e.g., the first one, the longest one, etc.)?
What is the maximum possible length of the input array?
Are we only allowed to flip *one* 0, or *at most one* 0, meaning that if there are no zeros to flip, should I return the length of the entire array if it contains only ones?

Brute Force Solution

Approach

The brute force approach to finding the maximum consecutive ones with one flip allowed means trying every possible flip. We'll go through each position, flip it, and see how many consecutive ones we get. Then, we'll pick the arrangement that gives us the most consecutive ones.

Here's how the algorithm would work step-by-step:

Go through each spot in the sequence, one at a time.
At each spot, imagine you flip a zero into a one.
Count how many ones are now in a row, including the one you just flipped.
Remember this count.
Move to the next spot and do the same thing: imagine flipping a zero, and count consecutive ones.
Once you've tried flipping every zero, compare all the counts you remembered.
The highest count you found is the answer: the maximum number of consecutive ones you can get by flipping one zero.

Code Implementation

def max_consecutive_ones_ii_brute_force(numbers):
    maximum_ones = 0
    for index in range(len(numbers)):
        # Try flipping each zero to one and count consecutive ones

        if numbers[index] == 0:
            temporary_numbers = numbers[:]
            temporary_numbers[index] = 1
            current_ones = 0
            
            count = 0
            for number_index in range(len(temporary_numbers)):
                if temporary_numbers[number_index] == 1:
                    count += 1
                    current_ones = max(current_ones, count)
                else:
                    # Reset count if we find a zero

                    count = 0
            maximum_ones = max(maximum_ones, current_ones)

    # If array has all ones, return the array size
    if 0 not in numbers:
        return len(numbers)

    return maximum_ones

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach iterates through each of the n elements of the input array. For each element, it simulates a flip and then counts the consecutive ones. In the worst case, counting consecutive ones involves traversing the entire array again, taking O(n) time. Since this counting process is nested within the outer loop that also iterates n times, the overall time complexity becomes O(n * n). This simplifies to O(n²).

Space Complexity

O(1) – The described brute force approach iterates through the input array of size N, but it only uses a few variables to store counts and the maximum. There are no auxiliary data structures like arrays, lists, or hash maps created that scale with the input size. Therefore, the space used is constant, regardless of the size of the input array.

Optimal Solution

Approach

The best way to solve this is to use a 'window' that expands and contracts as we go through the list. The key is to keep track of how many times we've 'flipped' a zero to a one within that window, ensuring we only flip one.

Here's how the algorithm would work step-by-step:

Imagine a window that slides across the numbers, showing us a slice of the list.
We'll expand the window to the right, counting how many ones are inside.
If we find a zero, we remember we've flipped one zero so far.
If we find a second zero, that means we've tried to flip two zeros, which is against the rules. So, we shrink the window from the left until we only have one flipped zero inside again.
As we slide the window, we keep track of the biggest window we've seen so far. That biggest window tells us the most consecutive ones we can have after flipping one zero.
By sliding and resizing the window smartly, we look at every possible group of numbers without checking extra groups, giving us the best answer quickly.

Code Implementation

def max_consecutive_ones_2(numbers):
    maximum_consecutive_ones = 0
    left_pointer = 0
    zero_count = 0

    for right_pointer in range(len(numbers)):
        if numbers[right_pointer] == 0:
            zero_count += 1

        # Shrink the window if more than one zero is found
        while zero_count > 1:
            if numbers[left_pointer] == 0:
                # Reduce zero count as it exits window.
                zero_count -= 1

            left_pointer += 1

        # Update the max length of consecutive ones
        maximum_consecutive_ones = max(
            maximum_consecutive_ones, right_pointer - left_pointer + 1
        )

    return maximum_consecutive_ones

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a sliding window approach, iterating through the input array nums of size n with two pointers (left and right). The right pointer expands the window, and the left pointer contracts it when more than one zero is encountered within the window. Each pointer moves from left to right at most n times. Therefore, the number of operations is directly proportional to the size of the input array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The described algorithm uses a sliding window approach and only maintains a few integer variables, such as the window's start and end indices, the count of flipped zeros within the window, and the maximum window size encountered so far. The number of variables used does not depend on the input array's size (N). Therefore, the auxiliary space remains constant regardless of the input size, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no ones.
Array with all zeros	Return 1 since we can flip one zero.
Array with all ones	Return the length of the array, as no flip is needed but allowed.
Array with a single zero	Return the length of the array since a single flip yields all ones.
Array with many consecutive zeros	The sliding window approach should efficiently handle this without integer overflow.
Input array contains non-binary values (not 0 or 1)	Treat non-binary values as zeros.
Integer overflow when calculating window size	The sliding window algorithm naturally avoids integer overflow by tracking indices.
Maximum size array with alternating 0s and 1s	The sliding window should still find the optimal solution within acceptable time complexity.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the input array is null or empty?
Can the input array contain values other than 0 and 1?
If there are multiple subarrays with the same maximum number of consecutive ones after flipping at most one 0, which one should I return (e.g., the first one, the longest one, etc.)?
What is the maximum possible length of the input array?
Are we only allowed to flip *one* 0, or *at most one* 0, meaning that if there are no zeros to flip, should I return the length of the entire array if it contains only ones?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each spot in the sequence, one at a time.
At each spot, imagine you flip a zero into a one.
Count how many ones are now in a row, including the one you just flipped.
Remember this count.
Move to the next spot and do the same thing: imagine flipping a zero, and count consecutive ones.
Once you've tried flipping every zero, compare all the counts you remembered.
The highest count you found is the answer: the maximum number of consecutive ones you can get by flipping one zero.

Code Implementation

def max_consecutive_ones_ii_brute_force(numbers):
    maximum_ones = 0
    for index in range(len(numbers)):
        # Try flipping each zero to one and count consecutive ones

        if numbers[index] == 0:
            temporary_numbers = numbers[:]
            temporary_numbers[index] = 1
            current_ones = 0
            
            count = 0
            for number_index in range(len(temporary_numbers)):
                if temporary_numbers[number_index] == 1:
                    count += 1
                    current_ones = max(current_ones, count)
                else:
                    # Reset count if we find a zero

                    count = 0
            maximum_ones = max(maximum_ones, current_ones)

    # If array has all ones, return the array size
    if 0 not in numbers:
        return len(numbers)

    return maximum_ones

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine a window that slides across the numbers, showing us a slice of the list.
We'll expand the window to the right, counting how many ones are inside.
If we find a zero, we remember we've flipped one zero so far.
If we find a second zero, that means we've tried to flip two zeros, which is against the rules. So, we shrink the window from the left until we only have one flipped zero inside again.
As we slide the window, we keep track of the biggest window we've seen so far. That biggest window tells us the most consecutive ones we can have after flipping one zero.
By sliding and resizing the window smartly, we look at every possible group of numbers without checking extra groups, giving us the best answer quickly.

Code Implementation

def max_consecutive_ones_2(numbers):
    maximum_consecutive_ones = 0
    left_pointer = 0
    zero_count = 0

    for right_pointer in range(len(numbers)):
        if numbers[right_pointer] == 0:
            zero_count += 1

        # Shrink the window if more than one zero is found
        while zero_count > 1:
            if numbers[left_pointer] == 0:
                # Reduce zero count as it exits window.
                zero_count -= 1

            left_pointer += 1

        # Update the max length of consecutive ones
        maximum_consecutive_ones = max(
            maximum_consecutive_ones, right_pointer - left_pointer + 1
        )

    return maximum_consecutive_ones

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there are no ones.
Array with all zeros	Return 1 since we can flip one zero.
Array with all ones	Return the length of the array, as no flip is needed but allowed.
Array with a single zero	Return the length of the array since a single flip yields all ones.
Array with many consecutive zeros	The sliding window approach should efficiently handle this without integer overflow.
Input array contains non-binary values (not 0 or 1)	Treat non-binary values as zeros.
Integer overflow when calculating window size	The sliding window algorithm naturally avoids integer overflow by tracking indices.
Maximum size array with alternating 0s and 1s	The sliding window should still find the optimal solution within acceptable time complexity.