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
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;
}
}