Max Consecutive Ones

Q: What is the time complexity of Max Consecutive Ones?

The one pass solution runs in O(n) time, because it reads each value once, and uses O(1) extra space: one counter for the current run and one for the best. Restarting the count at every index takes O(n²) on an array of all 1s.

Q: Why does the counter reset to 0 instead of 1?

The counter holds the length of the run that ends at the current index. When the value there is 0 , no run of 1s ends there, so the length is 0 . The next 1 raises it to 1 , the length of the new run.

Q: Is Max Consecutive Ones a sliding window problem?

You can see it as one: the window holds the current run, its right edge moves on every value, and a 0 moves the left edge past it. The window never shrinks step by step, so one counter replaces the two edges.

BeginnerArrays and strings

+10

You get an array nums in which every value is 0 or 1. A run is a stretch of 1s that sit next to each other with no 0 between them. Return the length of the longest run, or 0 if the array holds no 1 at all.

Function

findMaxConsecutiveOnes(nums: integer-array) → integer

numsinteger-array: an array of 0s and 1s
Returnsinteger: the length of the longest run of consecutive 1s

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
Every nums[i] is 0 or 1.

Examples

Input: nums = [1, 1, 0, 1, 1, 1, 0, 1]
Output: 3
Explanation: The 1s form three runs: indexes 0 to 1 (length 2), 3 to 5 (length 3) and index 7 alone (length 1). The longest has length 3.

Input: nums = [0, 1, 0, 1, 1]
Output: 2
Explanation: The single 1 at index 1 loses to the pair at indexes 3 and 4, so the answer is 2.

Input: nums = [0, 0, 0]
Output: 0
Explanation: There is no 1 anywhere, so there is no run and the answer is 0.

Follow-up

What if you may flip up to k zeros to ones? How long can the longest run get, and can you still find it in one pass?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A run ends the moment a 0 appears, so at each index you only need the length of the run ending there. One counter that grows on a 1 and resets on a 0 finds the longest run in a single pass.

Count forward from every index

Correct, but does not finish on the largest tests

Intuition

Try each index as a start and walk forward while you see 1s; the number of steps is the length of the run that starts there. The longest run starts at one of these indexes, so the largest count is the answer.

The walks overlap. On an array of n ones they take about n² / 2 steps, 2 × 10^8 for n = 2 × 10^4.

Algorithm

Set best = 0.
For every index start, set length = 0.
While start + length is inside the array and nums[start + length] is 1, add 1 to length.
Keep the larger of best and length.
Return best.

def findMaxConsecutiveOnes(nums):
    n = len(nums)
    best = 0
    for start in range(n):
        length = 0
        while start + length < n and nums[start + length] == 1:
            length += 1
        best = max(best, length)
    return best

One pass with a running count

Intuition

Keep current, the length of the run of 1s that ends at the index you are on. A 1 extends that run by one; a 0 ends it, so current drops to 0. Every run is measured at its last index, where current equals its full length, so the largest value current reaches is the answer.

On [1, 1, 0, 1, 1, 1, 0, 1], current takes the values 1, 2, 0, 1, 2, 3, 0, 1, and the largest is 3.

Algorithm

Set best = 0 and current = 0.
For each value in nums: if it is 1, add 1 to current and keep the larger of best and current.
If it is 0, set current = 0.
Return best.

def findMaxConsecutiveOnes(nums):
    best = 0
    current = 0
    for x in nums:
        if x == 1:
            current += 1
            best = max(best, current)
        else:
            # A 0 breaks the run.
            current = 0
    return best

Pitfalls and edge cases

Updating best only when you meet a 0. A run that reaches the end, as in [0, 1, 1], is never recorded. Update after every 1, or compare once more after the loop.
Not resetting current on a 0. Separate runs add up, and [1, 1, 0, 1, 1] returns 4.
Starting best at 1 or at nums[0]. [0, 0, 0] must return 0.
In Lua and R, where arrays start at 1, bounding the forward walk with < n instead of ≤ n. The last value is never read, so [0, 1] returns 0.

Frequently asked questions3

What is the time complexity of Max Consecutive Ones?

The one pass solution runs in O(n) time, because it reads each value once, and uses O(1) extra space: one counter for the current run and one for the best. Restarting the count at every index takes O(n²) on an array of all 1s.

Why does the counter reset to 0 instead of 1?

The counter holds the length of the run that ends at the current index. When the value there is 0, no run of 1s ends there, so the length is 0. The next 1 raises it to 1, the length of the new run.

Is Max Consecutive Ones a sliding window problem?

You can see it as one: the window holds the current run, its right edge moves on every value, and a 0 moves the left edge past it. The window never shrinks step by step, so one counter replaces the two edges.

def findMaxConsecutiveOnes(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output