LeetCode 485 - Max Consecutive Ones
The problem gives us a binary array named nums, where every element is either 0 or 1. Our task is to determine the maximum number of consecutive 1s that appear anywhere in the array.
Difficulty: 🟢 Easy
Topics: Array
Solution
Problem Understanding
The problem gives us a binary array named nums, where every element is either 0 or 1. Our task is to determine the maximum number of consecutive 1s that appear anywhere in the array.
In other words, we need to scan through the array and identify the longest uninterrupted sequence of 1s. A sequence ends whenever we encounter a 0. The final answer is the length of the longest such sequence.
For example, in the array [1,1,0,1,1,1], there are two groups of consecutive 1s:
- The first group is
[1,1], which has length2 - The second group is
[1,1,1], which has length3
Since 3 is larger, the correct answer is 3.
The constraints tell us that the array length can be as large as 10^5. This is important because it means we should avoid unnecessarily expensive algorithms such as checking every possible subarray. An efficient linear-time solution is preferred.
The input also guarantees that every element is either 0 or 1. This simplifies the logic significantly because we only need to distinguish between two cases:
- Continue a streak of consecutive
1s - Reset the streak when a
0appears
Several edge cases are important to consider upfront. The array might contain all 1s, meaning the answer is simply the entire array length. The array might contain all 0s, meaning the answer is 0. There may also be multiple streaks of equal length, and the algorithm must still return the correct maximum value. Since the minimum array size is 1, we never need to handle an empty input array.
Approaches
Brute Force Approach
A straightforward brute-force solution is to examine every possible starting position in the array and count how many consecutive 1s continue from that position.
For each index:
- If the current value is
1, continue moving forward until a0is found - Count the streak length
- Update the maximum streak seen so far
This works because every possible consecutive sequence of 1s is checked explicitly. However, the approach is inefficient because the same elements may be revisited many times.
Consider an array of all 1s:
[1,1,1,1,1,1]
Starting from index 0, we scan almost the entire array. Starting from index 1, we scan almost the entire remaining array again, and so on. This repeated work leads to quadratic time complexity.
With n up to 10^5, an O(n^2) solution is too slow.
Optimal Approach
The key observation is that we do not need to repeatedly rescan the array. We only need to keep track of two values while traversing once from left to right:
- The current streak length of consecutive
1s - The maximum streak length seen so far
Whenever we encounter:
- A
1, we extend the current streak - A
0, we reset the current streak to0
This works because consecutive sequences are naturally processed in a single pass. Every element contributes to the streak exactly once.
Since we only traverse the array one time and use constant extra space, this produces an optimal solution.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Repeatedly scans overlapping streaks of 1s |
| Optimal | O(n) | O(1) | Single pass while tracking current and maximum streaks |
Algorithm Walkthrough
Optimal Single-Pass Algorithm
- Initialize two variables:
current_streak = 0max_streak = 0
current_streak tracks the length of the current sequence of consecutive 1s. max_streak stores the largest sequence seen so far.
2. Traverse the array from left to right.
We process each element exactly once because the array only needs a single scan.
3. If the current element is 1, increment current_streak.
This means the current sequence of consecutive 1s continues.
4. After incrementing, compare current_streak with max_streak.
If the current streak is larger, update max_streak.
5. If the current element is 0, reset current_streak to 0.
A 0 breaks the consecutive sequence, so any future streak must start fresh.
6. Continue until the end of the array.
7. Return max_streak.
By the end of traversal, this variable contains the length of the longest consecutive sequence of 1s.
Why it works
The algorithm maintains an important invariant throughout execution:
current_streakalways represents the number of consecutive1s ending at the current positionmax_streakalways represents the largest streak encountered so far
Whenever a 0 appears, the current sequence becomes invalid and is reset. Since every element is processed once in order, every possible streak is accounted for exactly once. Therefore, the final max_streak is guaranteed to be correct.
Python Solution
from typing import List
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
current_streak = 0
max_streak = 0
for num in nums:
if num == 1:
current_streak += 1
max_streak = max(max_streak, current_streak)
else:
current_streak = 0
return max_streak
The implementation begins by initializing two counters. current_streak keeps track of the current run of consecutive 1s, while max_streak stores the best result found so far.
The loop iterates through every element in the array exactly once. If the current value is 1, the current streak is extended by incrementing current_streak. Immediately afterward, the algorithm updates max_streak if the current streak has become larger than the previous maximum.
If the current value is 0, the consecutive sequence is broken. The algorithm resets current_streak back to 0 because any future streak must begin after this point.
Finally, the method returns max_streak, which contains the longest sequence encountered during traversal.
Go Solution
func findMaxConsecutiveOnes(nums []int) int {
currentStreak := 0
maxStreak := 0
for _, num := range nums {
if num == 1 {
currentStreak++
if currentStreak > maxStreak {
maxStreak = currentStreak
}
} else {
currentStreak = 0
}
}
return maxStreak
}
The Go implementation follows the same logic as the Python version. Go uses a range loop to iterate through the slice. Since integers in this problem are very small, integer overflow is not a concern.
Go slices can technically be empty, but the problem guarantees at least one element. Even so, this implementation would still safely return 0 for an empty slice because the loop would simply not execute.
Worked Examples
Example 1
Input:
nums = [1,1,0,1,1,1]
Initial state:
current_streak = 0
max_streak = 0
| Index | Value | current_streak | max_streak | Explanation |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | Start first streak |
| 1 | 1 | 2 | 2 | Continue streak |
| 2 | 0 | 0 | 2 | Reset after zero |
| 3 | 1 | 1 | 2 | Start new streak |
| 4 | 1 | 2 | 2 | Continue streak |
| 5 | 1 | 3 | 3 | New maximum streak |
Final answer:
3
Example 2
Input:
nums = [1,0,1,1,0,1]
Initial state:
current_streak = 0
max_streak = 0
| Index | Value | current_streak | max_streak | Explanation |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | Start streak |
| 1 | 0 | 0 | 1 | Reset streak |
| 2 | 1 | 1 | 1 | Start new streak |
| 3 | 1 | 2 | 2 | Extend streak |
| 4 | 0 | 0 | 2 | Reset streak |
| 5 | 1 | 1 | 2 | Final streak |
Final answer:
2
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each element is processed exactly once |
| Space | O(1) | Only a few integer variables are used |
The algorithm is linear because it performs a single pass through the array. No nested loops or repeated scans are required. The space complexity is constant because the algorithm only stores two counters regardless of input size.
Test Cases
from typing import List
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
current_streak = 0
max_streak = 0
for num in nums:
if num == 1:
current_streak += 1
max_streak = max(max_streak, current_streak)
else:
current_streak = 0
return max_streak
solution = Solution()
assert solution.findMaxConsecutiveOnes([1,1,0,1,1,1]) == 3 # provided example 1
assert solution.findMaxConsecutiveOnes([1,0,1,1,0,1]) == 2 # provided example 2
assert solution.findMaxConsecutiveOnes([1]) == 1 # single element, one
assert solution.findMaxConsecutiveOnes([0]) == 0 # single element, zero
assert solution.findMaxConsecutiveOnes([1,1,1,1]) == 4 # all ones
assert solution.findMaxConsecutiveOnes([0,0,0,0]) == 0 # all zeros
assert solution.findMaxConsecutiveOnes([1,0,1,0,1,0]) == 1 # alternating pattern
assert solution.findMaxConsecutiveOnes([0,1,1,1,0]) == 3 # streak in middle
assert solution.findMaxConsecutiveOnes([1,1,1,0,0]) == 3 # streak at beginning
assert solution.findMaxConsecutiveOnes([0,0,1,1,1]) == 3 # streak at end
assert solution.findMaxConsecutiveOnes([1,1,0,1,1]) == 2 # multiple equal streaks
assert solution.findMaxConsecutiveOnes([1,1,1,1,0,1]) == 4 # longest streak before reset
| Test | Why |
|---|---|
[1,1,0,1,1,1] |
Validates standard multiple streak behavior |
[1,0,1,1,0,1] |
Confirms resets work correctly |
[1] |
Smallest valid input containing 1 |
[0] |
Smallest valid input containing 0 |
[1,1,1,1] |
Ensures full-array streak is handled |
[0,0,0,0] |
Ensures answer can correctly be 0 |
[1,0,1,0,1,0] |
Tests repeated resets |
[0,1,1,1,0] |
Tests streak surrounded by zeros |
[1,1,1,0,0] |
Tests streak at beginning |
[0,0,1,1,1] |
Tests streak at end |
[1,1,0,1,1] |
Tests equal-length streaks |
[1,1,1,1,0,1] |
Ensures earlier maximum is preserved |
Edge Cases
Array Contains Only Ones
An input such as [1,1,1,1] can expose bugs in implementations that only update the maximum streak when encountering a 0. In this case, the streak continues until the end of the array, so the implementation must continuously update the maximum during traversal. The provided solution handles this correctly by updating max_streak immediately whenever a 1 is processed.
Array Contains Only Zeros
An input such as [0,0,0] is important because there are no valid streaks of 1s at all. Some incorrect implementations may accidentally initialize the answer to 1 or fail to reset properly. The current implementation initializes both counters to 0 and only increments when encountering a 1, so the result correctly remains 0.
Longest Streak Appears at the End
An input such as [0,1,1,1] can break implementations that only finalize results when a streak ends. Since the longest streak reaches the final element, the algorithm must already be maintaining the maximum during iteration. The provided solution updates max_streak immediately after each 1, ensuring the final streak is counted correctly.
Multiple Equal-Length Streaks
An input such as [1,1,0,1,1] contains two streaks with the same maximum length. The algorithm should return the length itself, not care about which streak appears first. Since the implementation only tracks the numerical maximum, equal-length streaks are naturally handled correctly.