Max Consecutive Ones II — Medium Problem & Solution

Given a binary array nums, return the maximum number of consecutive 1s obtainable if you may flip at most one 0.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Sliding Window
Asked at: Amazon, Meta, Cognizant
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a binary array nums, return the maximum number of consecutive 1s obtainable if you may flip at most one 0.

Example 1

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: Flipping either 0 yields a run of four.

Example 2

Input: nums = [1,0,1,1,0,1]
Output: 4

Example 3

Input: nums = [0,0,0]
Output: 1
Explanation: One flip gives a single 1.

Constraints

1 <= nums.length <= 100000
nums[i] is 0 or 1

How to solve Max Consecutive Ones II

A window with at most one 0 is exactly a run of 1s plus one flip. Grow it on the right and repair from the left whenever a second 0 enters.

Approach

Track zeros, the number of 0s in the window.
On adding nums[r], bump zeros when it is 0.
While zeros > 1, advance the left edge, lowering zeros when the departing element was a 0.
Record the window's width.

Why it works

Removing elements never raises the 0 count, so the valid left edges for each right edge form a suffix and the left pointer moves forward only. The flip is free in the sense that any window with one 0 is realisable — flipping that 0 makes the whole window 1s.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

An all-1 array needs no flip, and the window naturally covers everything.
An all-0 array gives 1, not 0 — a flip is always available.
Allowing two 0s in the window over-counts; the bound is strict.

Reference solution

Python

from typing import List

def findMaxConsecutiveOnes(nums: List[int]) -> int:
    l = 0
    zeros = 0
    best = 0
    for r, v in enumerate(nums):
        if v == 0:
            zeros += 1
        while zeros > 1:
            if nums[l] == 0:
                zeros -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

JavaScript

var findMaxConsecutiveOnes = function(nums) {
    var l = 0, zeros = 0, best = 0;
    for (var r = 0; r < nums.length; r++) {
        if (nums[r] === 0) zeros++;
        while (zeros > 1) {
            if (nums[l] === 0) zeros--;
            l++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue