Jobs

Interviews

Discussions

Max Consecutive Ones

Easy

Asked by:

More companies

76 views

Topics:

Arrays

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

Example 1:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 2

Constraints:

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

Try coding it in LeetCode

Max Consecutive Ones

Easy

Asked by:

76 views

Topics:

Arrays

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

Example 1:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

Example 2:

Input: nums = [1,0,1,1,0,1]
Output: 2

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 should be the return value if the input array is empty?
Could the input array be extremely large? For instance, what are the constraints on its length?
Is it guaranteed that the array will only contain 0s and 1s, or could it contain other integer values as well?
What is the expected output if the array contains no ones at all?
Just to confirm, are we looking for a single integer representing the count, or something else like the start and end indices of the longest sequence?

Brute Force Solution

Approach

To find the longest stretch of ones, the brute force strategy is to look at every single possible group of numbers in our list, one by one. For each group, we'll check if it's made up of only ones, and then we'll remember the length of the longest one we've found so far.

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

First, consider every possible starting point in the list of numbers.
From each starting point, look at every possible end point that comes after it, creating a segment of numbers.
For every single one of these segments, examine each number inside it.
Check if all the numbers in that particular segment are ones.
If they are all ones, count how many numbers are in that segment.
Compare this count to the longest count of consecutive ones you've found so far.
If the current count is bigger, update your record for the longest stretch.
After checking every possible segment from every possible start and end point, the record you kept will be the final answer.

Code Implementation

def find_max_consecutive_ones_brute_force(numbers_list):
    maximum_length_of_ones = 0

    # Step 1: Consider every possible starting point in the list.
    for start_index in range(len(numbers_list)):

        # Step 2: From each start, consider every possible end point to form a segment.
        for end_index in range(start_index, len(numbers_list)):
            segment = numbers_list[start_index:end_index + 1]
            all_are_ones = True

            # Step 3 & 4: Check if all numbers in the current segment are ones.
            for number_in_segment in segment:
                if number_in_segment != 1:
                    all_are_ones = False
                    break

            # Step 5, 6, & 7: If the segment is all ones, update the maximum length found so far.
            if all_are_ones:
                current_segment_length = len(segment)
                if current_segment_length > maximum_length_of_ones:
                    maximum_length_of_ones = current_segment_length

    # Step 8: After checking all segments, we have the final answer.
    return maximum_length_of_ones

Big(O) Analysis

Time Complexity

O(n³) – The time complexity is driven by three nested levels of iteration. The first loop selects a starting point from n elements, and the second nested loop selects an ending point, defining all possible n² subarrays. For each of these subarrays, a third loop iterates through its elements to verify if they are all ones. This three-level nested structure results in a number of operations proportional to n * n * n, which simplifies to a time complexity of O(n³).

Space Complexity

O(1) – The brute-force approach described uses only a few variables to keep track of the process. One variable stores the length of the longest stretch of ones found so far, and other variables are used as loop counters for the start and end points of each segment. The amount of memory for these variables does not increase as the size of the input list, N, grows, resulting in constant auxiliary space usage.

Optimal Solution

Approach

The best way to solve this is to simply walk through the list of numbers one by one, keeping a running count of the consecutive ones we see. We'll also remember the highest count we've found so far, updating it whenever our current streak of ones gets bigger.

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

Imagine you have two counters: one for the current streak of ones and another for the longest streak seen so far. Both start at zero.
Look at the first number in the list.
If the number is a 1, increase the current streak counter by one.
If the number is a 0, it breaks the streak. You must reset the current streak counter back to zero.
After looking at each number, compare your current streak's count to the longest streak you've recorded so far.
If the current streak is longer, update the 'longest streak so far' to this new, higher number.
Continue this process until you have looked at every number in the list.
The number stored in your 'longest streak so far' counter at the end is the final answer.

Code Implementation

def find_max_consecutive_ones(list_of_numbers):
    current_streak_of_ones = 0
    longest_streak_so_far = 0
    
    for number in list_of_numbers:
        if number == 1:
            current_streak_of_ones += 1
        else:
            # A zero breaks the sequence, so we must reset the current streak count.

            current_streak_of_ones = 0
            
        # We need to check if the current streak is the new maximum after every number.

        if current_streak_of_ones > longest_streak_so_far:
            longest_streak_so_far = current_streak_of_ones

    # This ensures that a streak ending at the last element is also considered for the maximum.

    return longest_streak_so_far

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the need to examine each number in the input list exactly once. We use a single loop that iterates from the beginning to the end of the list. If the size of the list is n, this loop will run n times, and inside the loop, all operations like checking the number's value, incrementing a counter, or comparing two numbers are constant time operations. Therefore, the total number of operations is directly proportional to n, which simplifies to O(n).

Space Complexity

O(1) – The algorithm's space usage is constant because it only requires a few variables to store the current streak count and the maximum streak count found so far. The amount of memory used does not change regardless of the size of the input list, denoted by N. Therefore, the auxiliary space complexity is independent of the input size.

Edge Cases

Case	How to Handle
An empty input array	The loop will not execute, and the initial maximum count of 0 will be correctly returned.
A null input array	The solution should include a check to handle null input gracefully, often by returning 0 or throwing an exception.
An array containing only zeros	The current count of ones will never increment, resulting in the correct maximum of 0.
An array containing only ones	The current count will increment for every element, and the final maximum will correctly equal the array's length.
An array with a single element, which is a 1	The algorithm will correctly count one 1 and return a maximum of 1.
The longest sequence of ones is at the very beginning of the array	The maximum count is updated correctly as soon as the sequence is broken by a zero or the array ends.
The longest sequence of ones is at the very end of the array	A final check after the loop ensures the last computed sequence is compared against the overall maximum.
A very large input array near memory or time limits	A single-pass O(N) time and O(1) space solution handles large inputs efficiently without memory issues.

An empty input array

How to Handle:

The loop will not execute, and the initial maximum count of 0 will be correctly returned.

A null input array

How to Handle:

The solution should include a check to handle null input gracefully, often by returning 0 or throwing an exception.

An array containing only zeros

How to Handle:

The current count of ones will never increment, resulting in the correct maximum of 0.

An array containing only ones

How to Handle:

The current count will increment for every element, and the final maximum will correctly equal the array's length.

An array with a single element, which is a 1

How to Handle:

The algorithm will correctly count one 1 and return a maximum of 1.

The longest sequence of ones is at the very beginning of the array

How to Handle:

The maximum count is updated correctly as soon as the sequence is broken by a zero or the array ends.

The longest sequence of ones is at the very end of the array

How to Handle:

A final check after the loop ensures the last computed sequence is compared against the overall maximum.

A very large input array near memory or time limits

How to Handle:

A single-pass O(N) time and O(1) space solution handles large inputs efficiently without memory issues.

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 should be the return value if the input array is empty?
Could the input array be extremely large? For instance, what are the constraints on its length?
Is it guaranteed that the array will only contain 0s and 1s, or could it contain other integer values as well?
What is the expected output if the array contains no ones at all?
Just to confirm, are we looking for a single integer representing the count, or something else like the start and end indices of the longest sequence?

Brute Force Solution

Approach

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

First, consider every possible starting point in the list of numbers.
From each starting point, look at every possible end point that comes after it, creating a segment of numbers.
For every single one of these segments, examine each number inside it.
Check if all the numbers in that particular segment are ones.
If they are all ones, count how many numbers are in that segment.
Compare this count to the longest count of consecutive ones you've found so far.
If the current count is bigger, update your record for the longest stretch.
After checking every possible segment from every possible start and end point, the record you kept will be the final answer.

Code Implementation

def find_max_consecutive_ones_brute_force(numbers_list):
    maximum_length_of_ones = 0

    # Step 1: Consider every possible starting point in the list.
    for start_index in range(len(numbers_list)):

        # Step 2: From each start, consider every possible end point to form a segment.
        for end_index in range(start_index, len(numbers_list)):
            segment = numbers_list[start_index:end_index + 1]
            all_are_ones = True

            # Step 3 & 4: Check if all numbers in the current segment are ones.
            for number_in_segment in segment:
                if number_in_segment != 1:
                    all_are_ones = False
                    break

            # Step 5, 6, & 7: If the segment is all ones, update the maximum length found so far.
            if all_are_ones:
                current_segment_length = len(segment)
                if current_segment_length > maximum_length_of_ones:
                    maximum_length_of_ones = current_segment_length

    # Step 8: After checking all segments, we have the final answer.
    return maximum_length_of_ones

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have two counters: one for the current streak of ones and another for the longest streak seen so far. Both start at zero.
Look at the first number in the list.
If the number is a 1, increase the current streak counter by one.
If the number is a 0, it breaks the streak. You must reset the current streak counter back to zero.
After looking at each number, compare your current streak's count to the longest streak you've recorded so far.
If the current streak is longer, update the 'longest streak so far' to this new, higher number.
Continue this process until you have looked at every number in the list.
The number stored in your 'longest streak so far' counter at the end is the final answer.

Code Implementation

def find_max_consecutive_ones(list_of_numbers):
    current_streak_of_ones = 0
    longest_streak_so_far = 0
    
    for number in list_of_numbers:
        if number == 1:
            current_streak_of_ones += 1
        else:
            # A zero breaks the sequence, so we must reset the current streak count.

            current_streak_of_ones = 0
            
        # We need to check if the current streak is the new maximum after every number.

        if current_streak_of_ones > longest_streak_so_far:
            longest_streak_so_far = current_streak_of_ones

    # This ensures that a streak ending at the last element is also considered for the maximum.

    return longest_streak_so_far

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
An empty input array	The loop will not execute, and the initial maximum count of 0 will be correctly returned.
A null input array	The solution should include a check to handle null input gracefully, often by returning 0 or throwing an exception.
An array containing only zeros	The current count of ones will never increment, resulting in the correct maximum of 0.
An array containing only ones	The current count will increment for every element, and the final maximum will correctly equal the array's length.
An array with a single element, which is a 1	The algorithm will correctly count one 1 and return a maximum of 1.
The longest sequence of ones is at the very beginning of the array	The maximum count is updated correctly as soon as the sequence is broken by a zero or the array ends.
The longest sequence of ones is at the very end of the array	A final check after the loop ensures the last computed sequence is compared against the overall maximum.
A very large input array near memory or time limits	A single-pass O(N) time and O(1) space solution handles large inputs efficiently without memory issues.

An empty input array

How to Handle:

The loop will not execute, and the initial maximum count of 0 will be correctly returned.

A null input array

How to Handle:

The solution should include a check to handle null input gracefully, often by returning 0 or throwing an exception.

An array containing only zeros

How to Handle:

The current count of ones will never increment, resulting in the correct maximum of 0.

An array containing only ones

How to Handle:

The current count will increment for every element, and the final maximum will correctly equal the array's length.

An array with a single element, which is a 1

How to Handle:

The algorithm will correctly count one 1 and return a maximum of 1.

The longest sequence of ones is at the very beginning of the array

How to Handle:

The maximum count is updated correctly as soon as the sequence is broken by a zero or the array ends.

The longest sequence of ones is at the very end of the array

How to Handle:

A final check after the loop ensures the last computed sequence is compared against the overall maximum.

A very large input array near memory or time limits

How to Handle:

A single-pass O(N) time and O(1) space solution handles large inputs efficiently without memory issues.