Jobs

Interviews

Discussions

Max Consecutive Ones

Easy

Google

3 views

Topics:

Arrays

Given a binary array nums, return the maximum number of consecutive 1's in the array.

For example:

nums = [1,1,0,1,1,1] should return 3 because the longest consecutive sequence of 1s is [1, 1, 1].
nums = [1,0,1,1,0,1] should return 2 because the longest consecutive sequence of 1s is [1, 1].
nums = [0, 0, 0] should return 0 because there are no 1s.
nums = [1, 1, 1, 1] should return 4 because all elements are 1s.

Write a function that efficiently determines the maximum number of consecutive 1s in a given binary array. Consider the time and space complexity of your solution, and handle potential edge cases such as an empty array or an array containing only 0s. Provide code implementing this function.

Max Consecutive Ones

Easy

Google

3 views

Topics:

Arrays

Given a binary array nums, return the maximum number of consecutive 1's in the array.

For example:

nums = [1,1,0,1,1,1] should return 3 because the longest consecutive sequence of 1s is [1, 1, 1].
nums = [1,0,1,1,0,1] should return 2 because the longest consecutive sequence of 1s is [1, 1].
nums = [0, 0, 0] should return 0 because there are no 1s.
nums = [1, 1, 1, 1] should return 4 because all elements are 1s.

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 maximum possible length of the `nums` array?
Can the input array `nums` be empty or null?
Besides 0 and 1, can the input array contain any other values? What if the input contained other integers?
If the array contains no 1s, should I return 0?
Are we looking for the longest contiguous sequence of 1s or are non-contiguous sequences of 1s relevant to the solution?

Brute Force Solution

Approach

Imagine you have a row of light switches, some on and some off. The brute force approach involves checking every possible section of switches to find the longest continuous section of 'on' switches.

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

Start by looking at the very first switch. Is it on?
Then, look at the first two switches together. Are they both on? If so, how many in a row are on?
Continue this process, looking at the first three switches, then the first four, and so on, each time checking how many are on in a row, until you reach the end.
Next, start from the second switch. Look at the second switch by itself. Is it on?
Then, look at the second and third switches together. Are they both on? If so, how many in a row are on?
Keep going, looking at the second, third, and fourth switches, and so on.
Repeat this process, starting from each switch in the row, checking all possible groups of consecutive switches to see how many are on in a row.
As you check each group, remember the largest number of consecutive 'on' switches you've found so far.
At the very end, the largest number you remembered is your answer.

Code Implementation

def find_max_consecutive_ones_brute_force(numbers):
    maximum_consecutive_ones = 0

    for starting_index in range(len(numbers)):
        for ending_index in range(starting_index, len(numbers)):
            # We only want to evaluate if the current slice contains all 1s

            current_consecutive_ones = 0
            all_ones = True

            for index in range(starting_index, ending_index + 1):
                if numbers[index] == 1:
                    current_consecutive_ones += 1
                else:
                    all_ones = False
                    break

            # Only update max if the subsequence contains all 1's

            if all_ones:

                if current_consecutive_ones > maximum_consecutive_ones:

                    maximum_consecutive_ones = current_consecutive_ones

    return maximum_consecutive_ones

Big(O) Analysis

Time Complexity

O(n²) – The provided algorithm iterates through the array of size n, and for each element, it checks all consecutive subarrays starting from that element. For the first element, the algorithm potentially iterates through n elements; for the second, n-1 elements, and so on. This results in a total number of operations proportional to n + (n-1) + (n-2) + ... + 1, which approximates to n * (n+1) / 2. Therefore, the time complexity simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach that iterates through the input array, keeping track of the maximum consecutive ones found so far. It doesn't explicitly mention any auxiliary data structures like lists, hash maps, or recursion. The algorithm only requires a few constant extra variables to track the start and end positions of subarrays and the maximum count. Therefore, the auxiliary space used remains constant regardless of the input size N (where N is the number of switches), resulting in O(1) space complexity.

Optimal Solution

Approach

The goal is to find the longest continuous streak of 'ones' within a series. We can do this by sliding a 'window' across the series, keeping track of the current streak and updating the maximum streak found so far whenever a longer streak is encountered.

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

Start with a 'current count' and a 'maximum count', both set to zero.
Go through the series one element at a time.
If you find a 'one', increase the 'current count'.
If you find something that is not a 'one', compare the 'current count' to the 'maximum count'. If the 'current count' is larger, update the 'maximum count'. Then, reset the 'current count' back to zero.
After checking all the elements in the series, do one final check to see if the 'current count' is larger than the 'maximum count'. If it is, update the 'maximum count'.
The 'maximum count' will then hold the length of the longest continuous streak of 'ones'.

Code Implementation

def find_max_consecutive_ones(nums):
    current_consecutive_count = 0
    maximum_consecutive_count = 0

    for num in nums:
        if num == 1:
            current_consecutive_count += 1
        else:
            # Update max count if current is larger.
            if current_consecutive_count > maximum_consecutive_count:
                maximum_consecutive_count = current_consecutive_count

            # Reset current count for new streak.
            current_consecutive_count = 0

    # Check one last time after the loop.
    if current_consecutive_count > maximum_consecutive_count:
        maximum_consecutive_count = current_consecutive_count

    return maximum_consecutive_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n exactly once. For each element, it performs a constant amount of work: incrementing a counter, comparing counters, or resetting a counter. Therefore, the number of operations is directly proportional to the input size n, resulting in a linear time complexity.

Space Complexity

O(1) – The algorithm uses only two integer variables, 'current count' and 'maximum count', to store the current streak and the maximum streak found so far. The space required for these variables remains constant regardless of the size of the input array, N. No additional data structures are created that scale with the input. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there are no ones.
Array with all zeros	Return 0 as there are no consecutive ones.
Array with all ones	Return the length of the array as all elements are consecutive ones.
Array with alternating 0s and 1s (e.g., [1, 0, 1, 0, 1])	The algorithm should correctly identify the maximum consecutive ones sequence, which will be of length 1 in this case.
Array with a long sequence of ones at the beginning or end	The algorithm needs to correctly update the maximum count after encountering a zero or reaching the array's end.
Array with integer overflow if the array is extremely long and filled with ones in some languages	Using a language that supports arbitrarily large numbers like Python or use caution with data types like Java int.
Null input array	Throw an IllegalArgumentException or return 0 depending on the requirements.
Single element array with a zero	Return 0 since there is no consecutive ones.

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 maximum possible length of the `nums` array?
Can the input array `nums` be empty or null?
Besides 0 and 1, can the input array contain any other values? What if the input contained other integers?
If the array contains no 1s, should I return 0?
Are we looking for the longest contiguous sequence of 1s or are non-contiguous sequences of 1s relevant to the solution?

Brute Force Solution

Approach

Imagine you have a row of light switches, some on and some off. The brute force approach involves checking every possible section of switches to find the longest continuous section of 'on' switches.

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

Start by looking at the very first switch. Is it on?
Then, look at the first two switches together. Are they both on? If so, how many in a row are on?
Continue this process, looking at the first three switches, then the first four, and so on, each time checking how many are on in a row, until you reach the end.
Next, start from the second switch. Look at the second switch by itself. Is it on?
Then, look at the second and third switches together. Are they both on? If so, how many in a row are on?
Keep going, looking at the second, third, and fourth switches, and so on.
Repeat this process, starting from each switch in the row, checking all possible groups of consecutive switches to see how many are on in a row.
As you check each group, remember the largest number of consecutive 'on' switches you've found so far.
At the very end, the largest number you remembered is your answer.

Code Implementation

def find_max_consecutive_ones_brute_force(numbers):
    maximum_consecutive_ones = 0

    for starting_index in range(len(numbers)):
        for ending_index in range(starting_index, len(numbers)):
            # We only want to evaluate if the current slice contains all 1s

            current_consecutive_ones = 0
            all_ones = True

            for index in range(starting_index, ending_index + 1):
                if numbers[index] == 1:
                    current_consecutive_ones += 1
                else:
                    all_ones = False
                    break

            # Only update max if the subsequence contains all 1's

            if all_ones:

                if current_consecutive_ones > maximum_consecutive_ones:

                    maximum_consecutive_ones = current_consecutive_ones

    return maximum_consecutive_ones

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start with a 'current count' and a 'maximum count', both set to zero.
Go through the series one element at a time.
If you find a 'one', increase the 'current count'.
If you find something that is not a 'one', compare the 'current count' to the 'maximum count'. If the 'current count' is larger, update the 'maximum count'. Then, reset the 'current count' back to zero.
After checking all the elements in the series, do one final check to see if the 'current count' is larger than the 'maximum count'. If it is, update the 'maximum count'.
The 'maximum count' will then hold the length of the longest continuous streak of 'ones'.

Code Implementation

def find_max_consecutive_ones(nums):
    current_consecutive_count = 0
    maximum_consecutive_count = 0

    for num in nums:
        if num == 1:
            current_consecutive_count += 1
        else:
            # Update max count if current is larger.
            if current_consecutive_count > maximum_consecutive_count:
                maximum_consecutive_count = current_consecutive_count

            # Reset current count for new streak.
            current_consecutive_count = 0

    # Check one last time after the loop.
    if current_consecutive_count > maximum_consecutive_count:
        maximum_consecutive_count = current_consecutive_count

    return maximum_consecutive_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there are no ones.
Array with all zeros	Return 0 as there are no consecutive ones.
Array with all ones	Return the length of the array as all elements are consecutive ones.
Array with alternating 0s and 1s (e.g., [1, 0, 1, 0, 1])	The algorithm should correctly identify the maximum consecutive ones sequence, which will be of length 1 in this case.
Array with a long sequence of ones at the beginning or end	The algorithm needs to correctly update the maximum count after encountering a zero or reaching the array's end.
Array with integer overflow if the array is extremely long and filled with ones in some languages	Using a language that supports arbitrarily large numbers like Python or use caution with data types like Java int.
Null input array	Throw an IllegalArgumentException or return 0 depending on the requirements.
Single element array with a zero	Return 0 since there is no consecutive ones.