You are given a binary array nums
containing only 0s and 1s. Your task is to find the maximum number of consecutive 1s present in the array.
For example:
nums = [1, 1, 0, 1, 1, 1]
, the function should return 3
because the longest consecutive sequence of 1s is of length 3 (the last three elements).nums = [1, 0, 1, 1, 0, 1]
, the function should return 2
because the longest consecutive sequence of 1s is of length 2.nums = [0, 0, 0]
, the function should return 0
because there are no 1s.nums = [1, 1, 1, 1]
, the function should return 4
because all elements are 1s.nums = []
, the function should return 0
because the array is empty.Write a function that efficiently calculates the maximum number of consecutive 1s in a given binary array. Consider the time and space complexity of your solution.
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:
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:
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
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:
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
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. |