Max Consecutive Ones
Length of the longest run of 1s in a binary array.
2 min read
arrays counting
Problem#
Given a binary array nums, return the maximum number of consecutive 1s.
Examples#
[1,1,0,1,1,1]→3.[1,0,1,1,0,1]→2.
Constraints#
1 <= nums.length <= 10^5.
Hints#
Hint
One pass with a running counter, reset on zero.
Approach#
Track cur length of current run; reset to 0 on a zero, increment on a one. Update best after each update.
Solution#
class Solution {public: int findMaxConsecutiveOnes(vector<int>& nums) { int best = 0, cur = 0; for (int v : nums) { if (v == 1) { ++cur; best = max(best, cur); } else cur = 0; } return best; }};func findMaxConsecutiveOnes(nums []int) int { best, cur := 0, 0 for _, v := range nums { if v == 1 { cur++ if cur > best { best = cur } } else { cur = 0 } } return best}from typing import List
class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: best = cur = 0 for v in nums: if v == 1: cur += 1 if cur > best: best = cur else: cur = 0 return bestfunction findMaxConsecutiveOnes(nums) { let best = 0, cur = 0; for (const v of nums) { if (v === 1) { cur++; if (cur > best) best = cur; } else { cur = 0; } } return best;}class Solution { public int findMaxConsecutiveOnes(int[] nums) { int best = 0, cur = 0; for (int v : nums) { if (v == 1) { cur++; if (cur > best) best = cur; } else { cur = 0; } } return best; }}function findMaxConsecutiveOnes(nums: number[]): number { let best = 0, cur = 0; for (const v of nums) { if (v === 1) { cur++; if (cur > best) best = cur; } else { cur = 0; } } return best;}Editorial#
The simplest of run-length scans. Updating best only on increments is fine because zero-resets can’t improve best.
Complexity#
- Time: O(N).
- Space: O(1).
Concept revision#
Related#