Taro Logo

Max Consecutive Ones

Easy
Meta logo
Meta
Topics:
Arrays

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:

  1. If 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).
  2. If nums = [1, 0, 1, 1, 0, 1], the function should return 2 because the longest consecutive sequence of 1s is of length 2.
  3. If nums = [0, 0, 0], the function should return 0 because there are no 1s.
  4. If nums = [1, 1, 1, 1], the function should return 4 because all elements are 1s.
  5. If 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.

Solution


Naive Approach

The most straightforward approach is to iterate through the array and keep track of the current consecutive 1s and the maximum consecutive 1s seen so far. When we encounter a 0, we reset the current consecutive count to 0. Otherwise, we increment the count and update the maximum count if necessary.

Code (Python):

def find_max_consecutive_ones_naive(nums):
    max_count = 0
    current_count = 0
    for num in nums:
        if num == 1:
            current_count += 1
            max_count = max(max_count, current_count)
        else:
            current_count = 0
    return max_count

Complexity Analysis:

  • Time Complexity: O(n), where n is the length of the array, as we iterate through the array once.
  • Space Complexity: O(1), as we only use a constant amount of extra space for the max_count and current_count variables.

Optimal Approach

The naive approach is already quite efficient, so there's not a significant optimization to be made in terms of time complexity. The optimal approach is essentially the same as the naive approach, focusing on code clarity and conciseness.

Code (Python):

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
    return max(max_count, current_count)

Complexity Analysis:

  • Time Complexity: O(n), where n is the length of the array.
  • Space Complexity: O(1).

Edge Cases

  • Empty Array: If the input array is empty, the maximum number of consecutive 1s should be 0. The provided code handles this case correctly since the initial max_count is 0.
  • Array with all 0s: If the array contains only 0s, the code will also correctly return 0.
  • Array with all 1s: If the array contains only 1s, the code will iterate through all elements, incrementing current_count. After the loop, the max_count will be updated with current_count, effectively returning the length of the array.