Max Consecutive Ones
Max Consecutive Ones: given a binary array nums, return the maximum number of consecutive 1s.
- 1 <= nums.length <= 10⁵
- nums[i] is either 0 or 1.
Intuition
Max consecutive ones finds the longest run of 1s in a binary array. The naive instinct is to start at each position and count how far the run of ones extends — correct, but it re-examines the same elements repeatedly and costs O(n²) on an array of all ones.
The observation that removes the repetition is that a run ending at each position can be maintained incrementally:
- A 1 extends the current streak by one; a 0 ends it, so the counter resets to zero.
One pass, one counter, no re-scanning. Each element is examined exactly once because the streak length at position i is derived from the streak at i − 1 rather than recomputed from scratch.
The detail worth getting right is when to update the best. Compare after every increment, not only when a zero arrives or when the loop ends. If the array finishes on a run of ones — [0, 1, 1, 1] — a check that only fires at zeros never sees the final streak, and the answer comes out wrong.
Updating on every 1 costs one comparison per element and removes that entire class of bug, which is why it is worth preferring over the slightly cleverer version that only checks at boundaries.
An all-zeros array correctly yields 0, since the best is initialised to zero and no streak ever forms.
A running-streak counter — the simplest possible sliding window, where a zero resets the window to nothing. Worth recognising as the base case of the harder variants: max-consecutive-ones III allows flipping k zeros, at which point the reset becomes a shrink and you need a real two-pointer window.
Approach
Before reading on: you never need to look backwards here. Ask what single counter, and what one event, is enough to answer this in a single pass.
See why re-counting is wasteful
Counting the run starting at every index re-examines the same elements repeatedly — O(n²) on an array of all ones. Deriving each streak from the previous one removes that entirely.
Maintain one running streak
Keep a counter for the length of the run of ones ending at the current position. A 1 increments it; a 0 resets it to zero. This single variable is the whole state.
Update the best on every one
Compare the streak against the best each time it grows, not only at zeros or at the end. An array finishing on a run of ones would otherwise never have its final streak recorded.
Let zeros reset naturally
A zero sets the streak to 0 with no other handling. The next 1 starts a fresh run from there, so no explicit segment tracking is needed.
Check the empty and all-zero cases
Both return 0, since the best starts at zero and never rises. No special-casing is required — worth verifying rather than assuming.
Cost of the single pass
One traversal with constant work per element gives O(n) time and O(1) space, against O(n²) for the re-counting approach.
Solution & live demo
Common pitfalls
Updating the best only at the end
for n in nums:
if n == 1: streak += 1
else: streak = 0
return streak if n == 1:
streak += 1
best = max(best, streak)streak is reset by any later zero, so returning it reports the trailing run rather than the longest. The maximum has to be captured while the streak is still alive.
Forgetting to reset on a zero
if n == 1: streak += 1
if n == 1:
streak += 1
best = max(best, streak)
else:
streak = 0Without the reset the counter simply totals all ones in the array, ignoring whether they were consecutive at all.
Seeding best at 1
best = 1
best = streak = 0
An array of all zeros has a longest run of 0. Starting at 1 claims a run that never existed.
Edge cases
streak never resets, so best equals the array length.
streak stays 0 throughout; best returns 0.
best is updated on every 1, so a streak that ends only at the array's end is still captured.