AlgoViz
HomeArrays & Hashing

Maximum Consecutive Ones

Easy

Count the run, reset on a zero

Problem

Given a binary array nums, return the maximum number of consecutive 1s in the array. A binary array is an array that contains only 0s and 1s.

In simple words

Count 1s in a row, resetting to 0 whenever you hit a 0, and keep the best streak.

The idea

Keep a running count of the current streak of 1s and the best streak seen. A zero ends the streak, so reset the counter — the maximum is then just the largest value the counter ever reached.

The trick

  • Update the best on every increment, not only when a zero arrives, or a trailing run is missed.
  • O(n), single pass, no extra memory.
i
1
1
0
1
1
1
0
1
0
1
2
3
4
5
6
7
run1
best1

Step 1 of 9. 1 → run = 1, best = 1. Values: 1, 1, 0, 1, 1, 1, 0, 1. Pointers: i at index 0. run 1, best 1.

1/9
Optimal
timeO(n)spaceO(1)
1count = best = 02for x in nums:3  count = (x == 1) ? count + 1 : 04  best = max(best, count)5return best

Input

array
[1, 1, 0, 1, 1, 1, 0, 1]

Memory

i
= 0 [1]
run
1

Output

best
1
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 1, 0, 1, 1, 1]
Output:
3
Explanation:
The longest run of 1s at the end has length 3.

Example 2

Input:
nums = [1, 0, 1, 1, 0, 1]
Output:
2
Explanation:
The best unbroken streak of 1s is 2.

Example 3

Input:
nums = [0, 0, 0]
Output:
0
Explanation:
There are no 1s at all.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.