# Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

``````Input:
[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.``````

Note:

• The input array will only contain `0` and `1`.

• The length of input array is a positive integer and will not exceed 10,000

## Analysis

``````110111
^ ^
i = 0, j = 2

110111_
^  ^
i = 3, j = 6``````

The idea is to reset `maxHere` to 0 if we see 0, otherwise increase `maxHere` by 1

The max of all `maxHere` is the solution

``````110111
^ maxHere = 1

110111
.^ maxHere = 2

110111
..^ maxHere = 0

110111
...^ maxHere = 1

110111
....^ maxHere = 2

110111
.....^ maxHere = 3``````

## Solution

Two Pointers - Two pointers for left and right boundaries each (8ms AC) - O(n) time, O(1) space

``````class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int i = 0, j = 0;
int max = 0;
while (i < nums.length && j < nums.length) {
while (i < nums.length && nums[i] != 1) {
i++;
}
// i is the first index in the consecutive ones
j = i;
while (j < nums.length && nums[j] == 1) {
j++;
}
// j is now the first non-one index on the right of the last consecutive ones
max = Math.max(j - i, max);
// search for next consecutive ones
i = j;
}
return max;
}
}``````

Keeping track of length of current consecutive ones - O(n) time, O(1) space

``````class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int maxHere = 0, max = 0;
for (int n : nums)
max = Math.max(max, maxHere = n == 0 ? 0 : maxHere + 1);
return max;
}
}``````

OR easier to read version @shawngao:

``````public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int result = 0;
int count = 0;

for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
count++;
result = Math.max(count, result);
}
else count = 0;
}

return result;
}
}``````

## Reference

https://leetcode.com/problems/max-consecutive-ones/discuss/96693/Java-4-lines-concise-solution-with-explanation

Last updated