Max Consecutive Ones
Max Consecutive Ones is a easy arrays & hashing problem solved with the sliding window · variable pattern.
The best approach, optimal (single pass run counter), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (extend from every start) up.
Problem
You are given a binary array nums (every value is 0 or 1). Return the length of the longest block of consecutive 1s in it.
Examples
Example 1
- Input
nums = [1, 0, 1, 1, 0, 1, 1, 1, 1, 0]- Output
4- Why
- The run from index 5 to index 8 has four 1s in a row; the other runs are shorter.
Example 2
- Input
nums = [0, 0, 1]- Output
1- Why
- The only 1 forms a run of length 1.
Example 3
- Input
nums = [0, 0]- Output
0- Why
- There are no 1s at all.
Constraints
1 <= nums.length <= 10^5nums[i]is0or1.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (extend from every start) | O(n²) | O(1) |
| Optimal (single pass run counter) | O(n) | O(1) |
1Brute force (extend from every start)
O(n²)An all-ones array makes every start scan to the end.O(1)Two indices and the best length.From every index, count how many 1s follow without a break, and keep the largest count.
- For each i: j = i; while j < n and nums[j] == 1, j++.
- best = max(best, j - i).
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int best = 0;
for (int i = 0; i < nums.length; i++) {
int j = i;
while (j < nums.length && nums[j] == 1) j++;
best = Math.max(best, j - i);
}
return best;
}
}class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
best = 0
n = len(nums)
for i in range(n):
j = i
while j < n and nums[j] == 1:
j += 1
best = max(best, j - i)
return bestclass Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int best = 0, n = nums.size();
for (int i = 0; i < n; i++) {
int j = i;
while (j < n && nums[j] == 1) j++;
best = max(best, j - i);
}
return best;
}
};function findMaxConsecutiveOnes(nums) {
let best = 0;
for (let i = 0; i < nums.length; i++) {
let j = i;
while (j < nums.length && nums[j] === 1) j++;
best = Math.max(best, j - i);
}
return best;
}2Optimal (single pass run counter)
O(n)Each element is looked at once.O(1)Two integers.Walk once through the array with a counter for the current run. A 1 extends the run and may set a new best; a 0 resets the run to zero.
- run = 0, best = 0.
- For each x: if x == 1, run++ and best = max(best, run); else run = 0.
- Return best.
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int run = 0, best = 0;
for (int x : nums) {
if (x == 1) {
run++;
best = Math.max(best, run);
} else {
run = 0;
}
}
return best;
}
}class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
run = best = 0
for x in nums:
if x == 1:
run += 1
best = max(best, run)
else:
run = 0
return bestclass Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int run = 0, best = 0;
for (int x : nums) {
if (x == 1) {
run++;
best = max(best, run);
} else {
run = 0;
}
}
return best;
}
};function findMaxConsecutiveOnes(nums) {
let run = 0, best = 0;
for (const x of nums) {
if (x === 1) {
run++;
best = Math.max(best, run);
} else {
run = 0;
}
}
return best;
}Edge cases to test
- No 1s at all: answer 0
- All 1s: answer is the length
- The longest run touches the end of the array (do not forget the final run)
Hints
Hint 1
A run of 1s ends exactly when you see a 0. What should you remember at that moment?
Hint 2
Keep the length of the current run and the best length seen so far in a single pass.
FAQ
What is the best time complexity for Max Consecutive Ones?
Optimal (single pass run counter) runs in O(n) time and O(1) extra space. Each element is looked at once.
Which pattern does Max Consecutive Ones use?
It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.
Is there a brute force solution for Max Consecutive Ones?
Yes. Brute force (extend from every start) takes O(n²) time and O(1) space. From every index, count how many 1s follow without a break, and keep the largest count.
Which edge cases should I test for Max Consecutive Ones?
No 1s at all: answer 0; All 1s: answer is the length; The longest run touches the end of the array (do not forget the final run).