Coding

Max Consecutive Ones II

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

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

Input: nums = [1,0,1,1,0] Output: 4 Explanation: If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones. If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.

Input: nums = [1,0,1,1,0,1] Output: 4 Explanation: If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones. If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones. The max number of consecutive ones is 4.

**Input **: nums [1,1,0,0,1,1,0,0,1,1]

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

cpp

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        // Your code goes here
    }
};

java

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        // Your code goes here
    }
}

python

class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # Your code goes here
        return 0

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function(nums) {
    // Your code goes here
};

csharp

public class Solution
{
    public int FindMaxConsecutiveOnes(int[] nums)
    {
        // Your code goes here
    }
}

func findMaxConsecutiveOnes(nums []int) int {
	// Your code goes here
}

Stuck? Show a way to structure it+

01Keep a window with at most one zero.
02Expand the right pointer.
03Count zeros in the current window.
04Shrink from the left while zeros exceed one.
05Track the widest valid window.

Reference answer

Maintain a window [left, right] containing at most one zero, because that zero may be flipped. Expand right one element at a time and increment zeros when the new value is zero. Whenever zeros > 1, advance left, decrementing zeros when a zero leaves the window, until the invariant is restored. Every remaining window is feasible after at most one flip, so update the maximum with right - left + 1. This avoids trying each flip separately and works even when the best window contains no zero. Each pointer moves only forward, so time is O(N) and auxiliary space is O(1). State the invariant before coding; it is the key interview signal.

Then expect these follow-ups

How would you allow k flips?
Tests: generalization
How would you return the flipped index?
Tests: state tracking

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question