Max Consecutive Ones — Solution in Python, Java & C++
Max Consecutive Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays.
Max Consecutive Ones is an easy coding problem on arrays, asked in Amazon, Google, Microsoft and TCS interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: Amazon, Google, Microsoft, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a binary array nums, return the maximum number of consecutive 1s in the array.
Example 1
Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The last three elements form the longest run.
Example 2
Input: nums = [1,0,1,1,0,1]
Output: 2
Example 3
Input: nums = [0,0]
Output: 0
Constraints
1 <= nums.length <= 40nums[i] is either 0 or 1.
Hints for Max Consecutive Ones
Hint 1
Keep a running length that grows on a 1 and resets to 0 on a 0.
Hint 2
Update the best after every step, not only when a run ends — otherwise a run that reaches the end of the array is missed.
How to solve Max Consecutive Ones
Keep the length of the current run of 1s; it grows on a 1 and resets on a 0. Update the best after every element.
Approach
- Start
run = best = 0. - For each
x:run = run + 1ifx == 1else0; thenbest = max(best, run).
Why it works
Every maximal run of 1s is fully counted before a 0 resets it, and updating best on every step catches a run that reaches the end of the array.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Updating
bestonly when a 0 is seen misses a trailing run.
Reference solution
Python
def findMaxConsecutiveOnes(nums):
best = run = 0
for x in nums:
run = run + 1 if x == 1 else 0
if run > best:
best = run
return bestJava
public static int findMaxConsecutiveOnes(int[] nums) {
int best = 0, run = 0;
for (int x : nums) {
run = x == 1 ? run + 1 : 0;
if (run > best) best = run;
}
return best;
}C++
int findMaxConsecutiveOnes(vector<int>& nums) {
int best = 0, run = 0;
for (int x : nums) {
run = x == 1 ? run + 1 : 0;
if (run > best) best = run;
}
return best;
}JavaScript
var findMaxConsecutiveOnes = function(nums) {
let best = 0, run = 0;
for (let i = 0; i < nums.length; i++) {
run = nums[i] === 1 ? run + 1 : 0;
if (run > best) best = run;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays