Max Consecutive Ones

Difficulty: Easy | Acceptance: 65.10% | Paid: No Topics: Array

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

• Examples
• Constraints
• Approach 1: Single Pass
• Approach 2: Sliding Window
• Approach 3: Group By

Examples

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^5
nums[i] is either 0 or 1.

Single Pass

Intuition Iterate through the array once, keeping track of the current streak of consecutive 1s and the maximum streak seen so far.

Steps

• Initialize current count and max count to 0
• Iterate through each element in the array
• If the element is 1, increment current count
• If the element is 0, reset current count to 0
• Update max count with the maximum of max count and current count
• Return max count

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        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

• Time: O(n) where n is the length of the array
• Space: O(1) only using constant extra space
• Notes: This is the most optimal solution with a single pass through the array.

Sliding Window

Intuition Use a sliding window approach where we maintain a window containing only 1s and track the maximum window size.

Steps

• Initialize left pointer and max count to 0
• Iterate through the array with right pointer
• If we encounter a 0, move left pointer to right + 1
• Update max count with the maximum of max count and window size (right - left + 1)
• Return max count

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        left = 0
        max_count = 0
        
        for right in range(len(nums)):
            if nums[right] == 0:
                left = right + 1
            max_count = max(max_count, right - left + 1)
        
        return max_count

Complexity

• Time: O(n) where n is the length of the array
• Space: O(1) only using constant extra space
• Notes: This approach is conceptually similar to the single pass but uses the sliding window pattern.

Group By

Intuition Group consecutive 1s together and find the maximum group size.

Steps

• Initialize max count to 0
• Iterate through the array
• When we find a 1, count consecutive 1s until we hit a 0
• Update max count with the maximum of max count and current group size
• Return max count

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        max_count = 0
        i = 0
        n = len(nums)
        
        while i < n:
            if nums[i] == 1:
                count = 0
                while i < n and nums[i] == 1:
                    count += 1
                    i += 1
                max_count = max(max_count, count)
            else:
                i += 1
        
        return max_count

Complexity

• Time: O(n) where n is the length of the array
• Space: O(1) only using constant extra space
• Notes: This approach is less elegant than the single pass but demonstrates the grouping concept.