#485
Max Consecutive Ones
Easy Running counter
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a binary array, return the length of the longest run of consecutive 1s.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest unbroken streak of 1s.
Why this works: one counter grows on 1 and resets on 0; remember the best value it ever reached.
Example: [1, 1, 0, 1, 1, 1]
run: 1, 2, 0, 1, 2, 3best = 3
✦Hints open one at a time
Keep a counter of the current run.
Reset it to 0 when you see a 0, and update the best each step.
↗Approach
One pass with a current-run counter and a best-so-far value.
</>Solution (Java)
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int best = 0, run = 0;
for (int x : nums) {
run = (x == 1) ? run + 1 : 0;
best = Math.max(best, run); // update every step, not only on a 0
}
return best;
}
}!Common mistake
Updating the best only when a 0 appears, which misses a run that ends at the last element.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Arrays
