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 exactly once. It 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²) time 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 current value is 0 , no run of 1s ends there, so its length is 0 . The next 1 then raises it to 1 , which is the correct length of a new run.

Q: Is this a sliding window problem?

You can see it as one: the window holds the current run, the right edge moves on every value, and a 0 moves the left edge past it. Here the window never needs to shrink step by step, so a single counter replaces the two edges. The window view pays off in the harder version where you may flip up to k zeros to ones.

Q: How do you count consecutive 1s if you can flip one 0?

Keep two counters: the length of the run ending here with no flip, and with one flip already used. On a 1 both grow by one. On a 0, the flipped count becomes the plain count plus one, and the plain count resets to 0. The answer is the largest flipped count you see, still in one pass.

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 runs are the single 1 at index 1 and the pair at indexes 3 and 4. The pair wins with length 2.

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

+14 hidden tests on Submit

Follow-up

What if you may flip up to k zeros to ones? How long can the longest run of 1s 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 the only thing you need to know at any index is how long the run ending there is. Counting from scratch at every index repeats the same work again and again. One counter that grows on a 1 and resets on a 0 answers the question in a single pass.

Count forward from every index

Correct, but does not finish on the largest tests

Intuition

Every run starts somewhere. So try each index as a start and walk forward while you keep seeing 1s; the number of steps is the length of the run that starts there. The largest count over all starts is the answer. For [1, 1, 0, 1, 1, 1, 0, 1], the start at index 3 walks over three 1s before it meets the 0 at index 6, which gives 3.

The answer is correct because the longest run starts at one of the indexes you try, and from its first index the walk measures it exactly.

The cost hides in the overlap. In an array of n ones, the start at index 0 walks n steps, the next one n-1, and so on, about n² / 2 steps in total. For n = 2 × 10^4 that is 2 × 10^8 steps, too many for the time limit in slower languages.

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

Walk the array once and keep current, the length of the run of 1s that ends at the index you are on. A 1 extends that run, so current grows by one. A 0 ends it, so current drops back to 0. After every 1, compare current with best.

On [1, 1, 0, 1, 1, 1, 0, 1], current takes the values 1, 2, 0, 1, 2, 3, 0, 1, and the largest of them is 3. Every run is measured at its last index, where current equals its full length, so the best value seen is the longest run.

Each value is read once, which is O(n) time, and two integers are all the memory you need.

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

The one pass version is short, so the bugs come from where you update the answer.

Updating best only when you meet a 0. A run that reaches the end of the array, as in [0, 1, 1], is never recorded. Update after every 1, or compare once more after the loop.
Forgetting to reset current on a 0, which adds the 1s of separate runs together and returns 4 for [1, 1, 0, 1, 1].
Starting best at 1 or at nums[0]. An array of only 0s must return 0.
In Lua and R the array starts at index 1, so the forward walk checks start + length ≤ n instead of < n.

Frequently asked questions4

What is the time complexity of Max Consecutive Ones?

The one pass solution runs in O(n) time, because it reads each value exactly once. It 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²) time 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 current value is 0, no run of 1s ends there, so its length is 0. The next 1 then raises it to 1, which is the correct length of a new run.

Is this a sliding window problem?

You can see it as one: the window holds the current run, the right edge moves on every value, and a 0 moves the left edge past it. Here the window never needs to shrink step by step, so a single counter replaces the two edges. The window view pays off in the harder version where you may flip up to k zeros to ones.

How do you count consecutive 1s if you can flip one 0?

Keep two counters: the length of the run ending here with no flip, and with one flip already used. On a 1 both grow by one. On a 0, the flipped count becomes the plain count plus one, and the plain count resets to 0. The answer is the largest flipped count you see, still in one pass.

Python

def findMaxConsecutiveOnes(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

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

Expected