Max Consecutive Ones
Understanding the Problem
We have an array that only contains 0's and 1's, and we need to find the longest run of consecutive 1's. It is like counting the longest winning streak in a series of games where 1 means a win and 0 means a loss.
As we scan through the array, we maintain a running count of consecutive 1's. Every time we reach a 0, the streak breaks and the count resets. At each step, we record the largest count seen so far. The difficulty here is not the algorithm but implementing the scan without off-by-one errors.
Key Constraints:
1 <= nums.length <= 10^5→ With n up to 100,000, we need O(n) or O(n log n). An O(n^2) approach (checking every subarray) would be 10 billion operations, which is too slow.nums[i]is either0or1→ This is a binary array. We don't need to worry about negative numbers, large values, or any other edge cases related to element values. The only two states are "part of a streak" or "streak breaker."
Approach 1: Brute Force (Check All Subarrays)
Intuition
For every position in the array, count how long the run of consecutive 1's starting at that position is. The answer is the maximum of those counts across all starting positions. Pick a starting index, count how many 1's follow in a row, record that length, move to the next starting index, and repeat.
Algorithm
- Initialize
maxCount = 0to track the best streak found. - For each index
ifrom0ton - 1: - If
nums[i]is1, start counting consecutive 1's from indexi. - Use an inner loop starting at
i, incrementing a counter while elements are1. - Update
maxCountwith the streak length if it's larger. - Return
maxCount.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each starting index, we potentially scan the rest of the array. In the worst case (all 1's), the inner loop runs n, n-1, n-2, ... times, which sums to O(n^2).
- Space Complexity: O(1). Only a few integer variables are used. No extra data structures.
The brute force recounts the same 1's from every starting position inside a run. A single pass that keeps a running count, growing it on each 1 and resetting it on each 0, avoids that repeated work.
Approach 2: Single Pass (Running Counter)
Intuition
There is no need to restart counting from each position. Walk through the array once, keeping a running counter. On a 1, increment the counter. On a 0, the streak is broken, so reset the counter to 0. After each element, compare the current streak against the longest seen so far.
The counter maintains an invariant: count always holds the length of the run of 1's ending at the current position. On a 1 the run extends by one; on a 0 no run ends here, so the count drops to 0. Every maximal run of 1's ends at some index, and at that index count equals the full run length. Updating maxCount after every element therefore compares against each run's true length, including a run in the middle of the array that a later 0 breaks.
This is a simplified Kadane's algorithm. Kadane's tracks the best subarray sum ending at each position; here we track the longest run of 1's ending at each position. Both maintain a local running value, reset it at the right moment, and keep the global best.
Algorithm
- Initialize
maxCount = 0andcount = 0. - Iterate through each element in
nums. - If the element is
1, incrementcount. - If the element is
0, resetcountto0. - After each element, update
maxCount = max(maxCount, count). - Return
maxCount.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each element exactly once. The work per element is O(1): one comparison, one increment or reset, and one max update.
- Space Complexity: O(1). Only two integer variables (
countandmaxCount). No extra data structures regardless of input size.