Max Consecutive Ones II

Medium
802.

Max Consecutive Ones II

Max Consecutive Ones II is a medium coding problem on arrays, dynamic programming and sliding window, asked in Amazon, Meta and Cognizant interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Max Consecutive Ones II — Solution in Python, Java & C++

Max Consecutive Ones II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Max Consecutive Ones II is a medium coding problem on arrays, dynamic programming and sliding window, asked in Amazon, Meta and Cognizant interviews.

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

Hints for Max Consecutive Ones II

  1. Hint 1

    The flipped 0 sits inside the final run, so the run is a window containing at most one 0.

  2. Hint 2

    Grow the window on the right; while it holds two 0s, shrink it from the left.

  3. Hint 3

    The answer is the widest such window.

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

  1. Track zeros, the number of 0s in the window.
  2. On adding nums[r], bump zeros when it is 0.
  3. While zeros > 1, advance the left edge, lowering zeros when the departing element was a 0.
  4. 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

Java

public static int findMaxConsecutiveOnes(int[] nums) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] == 0) zeros++;
        while (zeros > 1) {
            if (nums[l] == 0) zeros--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

C++

int findMaxConsecutiveOnes(vector<int>& nums) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < (int) nums.size(); r++) {
        if (nums[r] == 0) zeros++;
        while (zeros > 1) {
            if (nums[l] == 0) zeros--;
            l++;
        }
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming