Max Consecutive Ones II — Flip One Zero, Track Its Index

Problem Statement#

Given a binary array nums, return the maximum number of consecutive ones if you can flip at most one zero.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is 0 or 1.
• Follow-up: solve it for a streaming input in O(1) space.

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

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

Why This Problem Matters#

LeetCode 487 — Max Consecutive Ones II — is a Medium that Microsoft, Meta, and Amazon love because it cleanly tests the sliding window pattern and ships with a follow-up the interviewer always asks: solve it for a stream. Candidates who memorise a generic template often pass the basic case but stumble on the stream version because they cannot articulate why the algorithm uses no extra memory.

The clever move is tracking the index of the last zero rather than a zero counter. With that single change, the shrink step becomes O(1) and the algorithm trivially supports a stream because it never looks back farther than the previous zero.

This problem is also the gateway to LeetCode 1004 (k flips), LeetCode 1493 (delete one element), LeetCode 424 (character replacement), and LeetCode 2024 (exam confusion). Mastering 487 unlocks an entire family of "longest valid window with bounded violations" questions.

The Core Insight#

The problem is equivalent to: find the longest subarray with at most one zero. Maintain a window [left, right]. When a new zero arrives, push left to last_zero + 1 so the older zero falls out and the new zero becomes the active flip.

For the streaming follow-up, you only need three integers: left, last_zero, and ans. You never reread any element beyond last_zero, so the array does not need to live in memory.

For the generalised k-flip version, replace last_zero with a deque of the most recent k zero indices. When the deque overflows, set left = deque.popleft() + 1. The k = 1 case collapses the deque to a single integer, which is the elegant trick of LC 487.

Visual Dry Run#

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

Final answer is 4.

Solution (Optimal)#

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        left = 0          # window left boundary
        last_zero = -1    # most recent zero index, -1 means none yet
        ans = 0
 
        for right, v in enumerate(nums):
            if v == 0:
                # Push left past the previous zero so only this zero remains.
                left = last_zero + 1
                last_zero = right
 
            ans = max(ans, right - left + 1)
 
        return ans

var findMaxConsecutiveOnes = function(nums) {
    let left = 0;
    let lastZero = -1;
    let ans = 0;
 
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) {
            left = lastZero + 1;
            lastZero = right;
        }
        ans = Math.max(ans, right - left + 1);
    }
 
    return ans;
};

Time: O(n) — single pass. Space: O(1) — three integer trackers, also satisfies the streaming follow-up.

Common Mistakes#

• Setting left = right + 1 instead of last_zero + 1 discards valid ones between the two zeros.
• Initialising last_zero = 0 instead of -1 shifts the first window incorrectly.
• Forgetting +1 in right - left + 1.
• Treating "at most one flip" as "exactly one flip" and missing the all-ones edge case.
• Using a while-loop shrink for k = 1 when a single assignment is sufficient.

Interview Tips#

• State the reduction: longest subarray with at most one zero.
• Highlight that tracking the zero index, not a counter, makes the shrink O(1).
• Volunteer the streaming follow-up before they ask, then explain why the same code already handles it.
• For the k flips generalisation, sketch the deque-of-zeros approach.

Follow-up Questions#

• LeetCode 1004 with k flips? Use a deque of last k zero indices and pop the front when it overflows.
• Streaming with k flips? Same deque, never store the array.
• Want the starting index of the best window? Track best_left whenever ans updates.
• LeetCode 1493 deletes one element? Answer is maxWindow - 1; for all-ones it becomes n - 1.
• Non-binary input? Treat any element failing the predicate as a zero; logic is unchanged.

Key Takeaways#

• LeetCode 487 is a Medium asked at Microsoft, Meta, and Amazon.
• The problem reduces to longest subarray with at most one zero.
• Tracking last_zero instead of a counter makes the shrink O(1).
• The same code answers the streaming follow-up in O(1) space.
• Window length is right - left + 1, not right - left.
• For k flips, replace the integer with a deque of the last k zero indices.
• LeetCode 1493 is the same window problem minus one for the deletion.