Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Max Consecutive Ones

EASYProblemSolveExternal Links

Description

Given a binary array nums (containing only 0s and 1s), return the maximum number of consecutive 1s in the array.

A consecutive sequence of 1s means a contiguous subarray where every element is 1, with no 0s breaking the chain. Your task is to find the longest such sequence and return its length.

Examples

Example 1

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

Output: 3

Explanation: There are two groups of consecutive 1s: the first group [1, 1] at indices 0-1 has length 2, and the second group [1, 1, 1] at indices 3-5 has length 3. The maximum is 3.

Example 2

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

Output: 2

Explanation: There are three groups of consecutive 1s: [1] at index 0 (length 1), [1, 1] at indices 2-3 (length 2), and [1] at index 5 (length 1). The maximum is 2.

Example 3

Input: nums = [0, 0, 0]

Output: 0

Explanation: There are no 1s in the array at all, so the maximum number of consecutive 1s is 0.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • nums[i] is either 0 or 1

Editorial

Brute Force

Intuition

The most straightforward way to find the longest run of consecutive 1s is to consider every possible starting position and try to extend a streak from there.

Imagine you are walking along a row of light bulbs. Some are on (1) and some are off (0). You stop at each ON bulb and count how many consecutive ON bulbs follow before you hit an OFF bulb or the end. After checking every starting position, you report the longest streak you found.

For each index i where nums[i] == 1, start a new inner loop from i and keep counting while you see 1s. When you hit a 0 or the array ends, record the streak length and compare it with your best so far.

Step-by-Step Explanation

Let's trace through with nums = [1, 0, 1, 1, 0, 1]:

Step 1: Start at i=0. nums[0]=1. Begin counting from index 0: j=0 (1), j=1 (0 — stop). Streak = 1. Update max_len = 1.

Step 2: Move to i=1. nums[1]=0. Skip — a streak cannot start with 0.

Step 3: Move to i=2. nums[2]=1. Begin counting from index 2: j=2 (1), j=3 (1), j=4 (0 — stop). Streak = 2. Update max_len = 2.

Step 4: Move to i=3. nums[3]=1. Begin counting from index 3: j=3 (1), j=4 (0 — stop). Streak = 1. max_len stays 2.

Step 5: Move to i=4. nums[4]=0. Skip.

Step 6: Move to i=5. nums[5]=1. Begin counting from index 5: j=5 (1), j=6 (end — stop). Streak = 1. max_len stays 2.

Result: max_len = 2.

Brute Force — Try Every Starting Position — For each index with a 1, count how far the consecutive streak extends. Track the longest streak found so far.

Algorithm

  1. Initialize max_len = 0
  2. For each index i from 0 to n-1:
    a. If nums[i] == 0, skip to next i
    b. Start inner loop from j = i, count while nums[j] == 1
    c. streak = j - i
    d. Update max_len = max(max_len, streak)
  3. Return max_len

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int n = nums.size();
        int max_len = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int streak = 0;
            for (int j = i; j < n && nums[j] == 1; j++) {
                streak++;
            }
            max_len = max(max_len, streak);
        }
        
        return max_len;
    }
};
class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        n = len(nums)
        max_len = 0
        
        for i in range(n):
            if nums[i] == 0:
                continue
            streak = 0
            j = i
            while j < n and nums[j] == 1:
                streak += 1
                j += 1
            max_len = max(max_len, streak)
        
        return max_len
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int n = nums.length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int streak = 0;
            for (int j = i; j < n && nums[j] == 1; j++) {
                streak++;
            }
            maxLen = Math.max(maxLen, streak);
        }
        
        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n²) in the worst case

Consider an array of all 1s like [1, 1, 1, ..., 1]. For i=0, the inner loop runs n times. For i=1, it runs n-1 times. For i=2, n-2 times, and so on. Total iterations: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²).

For typical inputs with mixed 0s and 1s, the inner loop is shorter, but worst case is quadratic.

Space Complexity: O(1)

We only use a few integer variables (max_len, streak, i, j). No extra data structures.

Why This Approach Is Not Efficient

The brute force approach does redundant work. When we start a streak at index i and count forward to index j (where the streak breaks), we already know the exact length of that consecutive block. But in the next iteration, when i moves to i+1, we start re-counting from within the same block — work we already did!

For example, in [1, 1, 1, 0], starting at i=0 tells us the streak is length 3. Starting at i=1, we re-discover a streak of length 2 — which is already inside the streak we just measured. Starting at i=2, we find length 1 — again redundant.

The key insight: once you've counted a streak, you already know where it ends. Instead of restarting from every index inside the streak, you can skip ahead to where the streak broke. Better yet, you can process the entire array in a single left-to-right pass: maintain a running counter that increments on 1s and resets on 0s. This eliminates all redundant recounting and reduces time from O(n²) to O(n).

Optimal Approach - Single Pass Counter

Intuition

Instead of trying every starting position, we can solve this in a single sweep through the array by maintaining two simple variables:

  1. current_count — the length of the current consecutive 1s streak we're in the middle of
  2. max_count — the longest streak we've seen so far

As we walk through the array from left to right:

  • If we see a 1, extend the current streak: increment current_count by 1. Then check if this streak is now the longest — update max_count if so.
  • If we see a 0, the current streak is broken: reset current_count to 0.

Think of it like counting consecutive rainy days on a calendar. You flip through each day. If it rained, your 'rain streak' counter goes up by one and you check if it beats your personal record. If it was sunny, you reset the counter to zero. By the time you reach December 31st, your record holds the answer — and you only looked at each day once.

This approach processes each element exactly once with constant work, giving us O(n) time.

Step-by-Step Explanation

Let's trace through with nums = [1, 1, 0, 1, 1, 1]:

Step 1: Initialize current_count = 0, max_count = 0.

Step 2: Process nums[0] = 1. It's a 1 → increment current_count to 1. Update max_count = max(0, 1) = 1.

Step 3: Process nums[1] = 1. It's a 1 → increment current_count to 2. Update max_count = max(1, 2) = 2.

Step 4: Process nums[2] = 0. It's a 0 → reset current_count to 0. Streak broken. max_count stays 2.

Step 5: Process nums[3] = 1. It's a 1 → increment current_count to 1. max_count = max(2, 1) = 2. A new streak begins, but hasn't beaten the record yet.

Step 6: Process nums[4] = 1. It's a 1 → increment current_count to 2. max_count = max(2, 2) = 2. Tied with record.

Step 7: Process nums[5] = 1. It's a 1 → increment current_count to 3. max_count = max(2, 3) = 3. New record!

Step 8: Array exhausted. Return max_count = 3.

Single Pass Counter — Track Streak and Record — Watch how current_count grows on each 1, resets on each 0, and max_count remembers the longest streak seen — all in one left-to-right scan.

Algorithm

  1. Initialize current_count = 0 and max_count = 0
  2. For each element num in the array:
    • If num == 1:
      • Increment current_count by 1
      • Update max_count = max(max_count, current_count)
    • Else (num == 0):
      • Reset current_count = 0
  3. Return max_count

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int currentCount = 0;
        int maxCount = 0;
        
        for (int num : nums) {
            if (num == 1) {
                currentCount++;
                maxCount = max(maxCount, currentCount);
            } else {
                currentCount = 0;
            }
        }
        
        return maxCount;
    }
};
class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        current_count = 0
        max_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
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int currentCount = 0;
        int maxCount = 0;
        
        for (int num : nums) {
            if (num == 1) {
                currentCount++;
                maxCount = Math.max(maxCount, currentCount);
            } else {
                currentCount = 0;
            }
        }
        
        return maxCount;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array exactly once, visiting each of the n elements one time. For each element, we perform constant-time operations: one comparison, one increment or reset, and one max update. Total: n × O(1) = O(n).

This is optimal — we must examine every element at least once to know the answer (the longest streak could involve any element), so O(n) is a lower bound.

Space Complexity: O(1)

We use only two integer variables (current_count and max_count) regardless of input size. No additional arrays, hash maps, or data structures are needed.