Max Consecutive Ones II

Max Consecutive Ones II

What is this problem about?

The Max Consecutive Ones II problem is a step up from the basic version. You are given a binary array, but this time, you are allowed to flip at most one 0 into a 1. Your goal is to find the maximum number of consecutive 1s you can achieve in the array after using this single flip.

Why is this asked in interviews?

This problem introduces the candidate to the concept of constraint-based optimization. Interviewers ask it because it bridges the gap between simple array traversal and the highly important Sliding Window technique. It tests whether you can maintain historical state (the length of the sequence before the flip) and combine it with current state (the length after the flip) seamlessly.

Algorithmic pattern used

This problem is perfectly solved using the Sliding Window (Two Pointers) pattern. We maintain a window using a left and right pointer. As the right pointer moves, we expand the window. We also keep a counter of how many 0s are currently inside our window. If the zero-count exceeds our allowance (which is 1), the window becomes invalid. We then move the left pointer forward until we drop a 0 out of our window, making it valid again. We track the maximum window size.

Example explanation

Array: [1, 0, 1, 1, 0]

• right=0 (1): zeros=0. Window [1]. Max = 1.
• right=1 (0): zeros=1. Window [1, 0]. Max = 2. (We used our flip!)
• right=2 (1): zeros=1. Window [1, 0, 1]. Max = 3.
• right=3 (1): zeros=1. Window [1, 0, 1, 1]. Max = 4.
• right=4 (0): zeros=2. Invalid! We must shrink. Move left forward.
  • left=0 (1): drops 1. Window [0, 1, 1, 0]. zeros=2. Still invalid.
  • left=1 (0): drops 0. Window [1, 1, 0]. zeros=1. Valid! The maximum length recorded was 4.

Common mistakes candidates make

Candidates sometimes try to solve this by splitting the array by 0s and keeping an array of segment lengths, then adding adjacent segments together. While this works, it uses $O(N)$ extra space and requires multiple passes. The Sliding Window approach is vastly superior because it solves the problem in a single pass with strict $O(1)$ space.

Interview preparation tip

When studying the Max Consecutive Ones II interview pattern, write your sliding window template dynamically so it handles a budget of k flips instead of hardcoding it for 1. If you write while (zero_count > 1), changing that 1 to k instantly solves the harder "Max Consecutive Ones III" problem. Mastering this generic template makes you look like a pro.