LeetCode 485: Max Consecutive Ones

Problem Restatement

We are given a binary array nums.

A binary array contains only:

We need to return the maximum number of consecutive 1s in the array. The official problem statement asks for the maximum number of consecutive 1s in a binary array.

Input and Output

Function shape:

def findMaxConsecutiveOnes(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [1, 1, 0, 1, 1, 1]

There are two runs of 1s:

[1, 1]       length 2
[1, 1, 1]    length 3

The longest run has length 3.

Answer:

3

Example 2:

nums = [1, 0, 1, 1, 0, 1]

The runs of 1s have lengths:

1, 2, 1

Answer:

2

First Thought: Split Into Groups

One way is to join the array into a string and split on 0.

For example:

nums = [1, 1, 0, 1, 1, 1]

becomes:

"110111"

Split by 0:

"11", "111"

The answer is the longest piece length.

class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        s = "".join(str(x) for x in nums)
        groups = s.split("0")
        return max(len(group) for group in groups)

This works, but it builds extra strings. We can solve the problem directly in one scan.

Key Insight

A consecutive run of 1s continues while we keep seeing 1.

When we see 0, the current run ends.

So we only need two counters:

When we see 1, increment current.

When we see 0, reset current to 0.

After every 1, update best.

Algorithm

Initialize:

current = 0
best = 0

Then scan every number in nums.

If the number is 1:

current += 1
best = max(best, current)

If the number is 0:

current = 0

Return best.

Correctness

The variable current always stores the length of the run of consecutive 1s ending at the current position.

If the current value is 1, then the previous run extends by one, so incrementing current is correct.

If the current value is 0, then no run of 1s can end at this position, so resetting current to 0 is correct.

The variable best stores the maximum value of current seen so far. Since every run of 1s ends at some position, the algorithm considers the length of every run when updating best.

Therefore, after scanning the whole array, best is exactly the maximum number of consecutive 1s.

Complexity

Implementation

class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        current = 0
        best = 0

        for num in nums:
            if num == 1:
                current += 1
                best = max(best, current)
            else:
                current = 0

        return best

Code Explanation

The current streak starts at zero:

current = 0

The best answer also starts at zero:

best = 0

When we see a 1, the current streak grows:

current += 1

Then we update the best result:

best = max(best, current)

When we see a 0, the streak is broken:

current = 0

After the loop, best is the longest streak.

Testing

def run_tests():
    s = Solution()

    assert s.findMaxConsecutiveOnes([1, 1, 0, 1, 1, 1]) == 3
    assert s.findMaxConsecutiveOnes([1, 0, 1, 1, 0, 1]) == 2
    assert s.findMaxConsecutiveOnes([0, 0, 0]) == 0
    assert s.findMaxConsecutiveOnes([1, 1, 1]) == 3
    assert s.findMaxConsecutiveOnes([0, 1, 1, 0, 1]) == 2
    assert s.findMaxConsecutiveOnes([1]) == 1
    assert s.findMaxConsecutiveOnes([0]) == 0

    print("all tests passed")

run_tests()

Test meaning: