Given a binary array nums
, can you find the maximum number of consecutive 1's in the array?
Here are some examples:
nums = [1,1,0,1,1,1]
The function should return 3 because the longest consecutive sequence of 1's is [1,1,1]
.
nums = [1,0,1,1,0,1]
The function should return 2 because the longest consecutive sequence of 1's is [1,1]
.
nums = [0,0,0]
The function should return 0 because there are no 1's.
nums = [1,1,1,1,1]
The function should return 5 because the array consists entirely of 1's.
Can you provide an efficient algorithm to solve this problem? What is the time and space complexity of your solution?
The brute force solution involves iterating through the array and, for each element, checking the consecutive 1s starting from that element. We keep track of the maximum count found so far.
max_count
to 0.i = 0
to n - 1
.i
, initialize current_count
to 0.i
is within the bounds of the array and nums[i]
is 1, increment current_count
and i
.max_count
with the maximum of max_count
and current_count
.max_count
.def find_max_consecutive_ones_brute_force(nums):
max_count = 0
n = len(nums)
for i in range(n):
current_count = 0
j = i
while j < n and nums[j] == 1:
current_count += 1
j += 1
max_count = max(max_count, current_count)
return max_count
O(n^2) in the worst case, where n is the length of the array. This is because, for each element, we might iterate through the rest of the array.
O(1), as we only use a constant amount of extra space.
A more efficient solution involves iterating through the array only once, keeping track of the current consecutive 1s count and updating the maximum count as we go.
max_count
to 0 and current_count
to 0.i = 0
to n - 1
.nums[i]
is 1, increment current_count
.nums[i]
is 0, update max_count
with the maximum of max_count
and current_count
, and reset current_count
to 0.max_count
one last time to account for the case where the array ends with consecutive 1s.max_count
.def find_max_consecutive_ones_optimal(nums):
max_count = 0
current_count = 0
for num in nums:
if num == 1:
current_count += 1
else:
max_count = max(max_count, current_count)
current_count = 0
max_count = max(max_count, current_count)
return max_count
O(n), where n is the length of the array. This is because we iterate through the array only once.
O(1), as we only use a constant amount of extra space.
These edge cases are handled correctly by both the brute force and optimal solutions.