LeetCode 487: Max Consecutive Ones II

Problem Restatement

We are given a binary array nums.

We may flip at most one 0 into 1.

Return the maximum number of consecutive 1s we can get after doing this optimally. The array length is at most 10^5, and every element is either 0 or 1.

Input and Output

Function shape:

def findMaxConsecutiveOnes(nums: list[int]) -> int:
    ...

Examples

Example 1:

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

If we flip the first 0:

[1, 1, 1, 1, 0]

The longest run has length 4.

If we flip the second 0:

[1, 0, 1, 1, 1]

The longest run has length 3.

Answer:

4

Example 2:

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

Flipping either zero can give a run of length 4.

Answer:

4

First Thought: Try Every Zero

One direct idea is to try flipping each 0.

For every zero index:

1. Pretend this zero becomes 1.
2. Count the longest run of 1s.
3. Keep the best answer.

This works, but it can scan the array again for each zero.

In the worst case, there may be O(n) zeroes, and each check costs O(n).

So the total cost can become:

O(n^2)

That is too slow for n = 100000.

Key Insight

After flipping at most one 0, any valid consecutive block may contain at most one zero.

So the problem becomes:

Find the longest contiguous subarray containing at most one 0.

This is a sliding window problem.

We keep a window:

nums[left:right + 1]

The window is valid while it contains at most one zero.

If adding nums[right] makes the window contain two zeroes, we move left rightward until the window becomes valid again.

Algorithm

Initialize:

left = 0
zeros = 0
best = 0

Scan right from left to right.

For each nums[right]:

1. If it is 0, increment zeros.
2. While zeros > 1, move left forward.
3. If the removed value was 0, decrement zeros.
4. Update best with the current window length.

The window length is:

right - left + 1

Correctness

The algorithm maintains a window with at most one zero.

When nums[right] is added, the zero count is updated. If the window has more than one zero, moving left forward removes elements from the window until at most one zero remains.

Therefore, after the shrinking step, the current window is always a valid subarray that can be turned into all 1s by flipping at most one zero.

For each right endpoint, the algorithm keeps the leftmost possible left that makes the window valid. That gives the longest valid window ending at right.

Since every possible answer has some right endpoint, and the algorithm checks the best valid window for every right endpoint, the maximum recorded length is the required answer.

Complexity

Implementation

class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        left = 0
        zeros = 0
        best = 0

        for right, num in enumerate(nums):
            if num == 0:
                zeros += 1

            while zeros > 1:
                if nums[left] == 0:
                    zeros -= 1
                left += 1

            best = max(best, right - left + 1)

        return best

Code Explanation

The left boundary starts at the beginning:

left = 0

The window initially has no zeroes:

zeros = 0

As we expand the right side:

for right, num in enumerate(nums):

we count zeroes:

if num == 0:
    zeros += 1

If the window has two zeroes, it can no longer be fixed with one flip:

while zeros > 1:

So we move the left boundary. If we remove a zero, the zero count decreases:

if nums[left] == 0:
    zeros -= 1
left += 1

Now the window is valid again, so we update the answer:

best = max(best, right - left + 1)

Stream-Friendly Implementation

The follow-up asks what happens if numbers arrive one by one and we cannot store the whole array.

For at most one flipped zero, we only need the position of the previous zero.

class Solution:
    def findMaxConsecutiveOnes(self, nums: list[int]) -> int:
        left = 0
        last_zero = -1
        best = 0

        for right, num in enumerate(nums):
            if num == 0:
                left = last_zero + 1
                last_zero = right

            best = max(best, right - left + 1)

        return best

When we see a new zero, the previous zero can no longer stay in the same valid window. So the next valid window must start after the previous zero.

Testing

def run_tests():
    s = Solution()

    assert s.findMaxConsecutiveOnes([1, 0, 1, 1, 0]) == 4
    assert s.findMaxConsecutiveOnes([1, 0, 1, 1, 0, 1]) == 4
    assert s.findMaxConsecutiveOnes([1, 1, 1]) == 3
    assert s.findMaxConsecutiveOnes([0, 0, 0]) == 1
    assert s.findMaxConsecutiveOnes([0]) == 1
    assert s.findMaxConsecutiveOnes([1]) == 1
    assert s.findMaxConsecutiveOnes([1, 1, 0, 1, 1, 1]) == 6

    print("all tests passed")

run_tests()

Test meaning: