Problem Description

Given a binary array nums (an array containing only 0s and 1s), you are allowed to flip at most one 0 to 1. Your task is to find the maximum number of consecutive 1s in the array after performing at most one flip.

• You may choose not to flip any 0 if it does not increase the maximum consecutive 1s.
• There is only one array as input, and you should return a single integer as output.
• The input array can be of any length, including empty or containing all 1s or all 0s.
• Each element in nums is either 0 or 1.
• Flipping means changing a single 0 to 1; you cannot flip a 1 to 0.

Thought Process

To solve this problem, let's first consider the brute-force approach: For every 0 in the array, flip it to 1, then scan the array to find the longest sequence of consecutive 1s. Keep track of the maximum found. But this would be inefficient, especially for large arrays, since for each 0 we potentially scan the whole array.

Instead, let's look for an optimized approach. The key is to realize that we want to find the largest window (subarray) that contains at most one 0. This is a classic sliding window problem: maintain a window with at most one 0 inside, expand the window as much as possible, and whenever you hit more than one 0, move the left edge of the window forward until you have at most one 0 again.

This way, we can efficiently find the answer in a single pass through the array.

Solution Approach

• Sliding Window Technique:
  • Use two pointers, left and right, to represent the current window in the array.
  • Keep a count of how many 0s are in the current window (let's call it zero_count).
  • Iterate right from the start to the end of the array, expanding the window.
  • Each time you include a 0 at right, increment zero_count.
  • If zero_count exceeds 1, move the left pointer to the right until zero_count is at most 1 (i.e., shrink the window from the left).
  • At each step, update the maximum window size found so far.
• Why This Works:
  • The window always contains at most one 0, which is the only one you are allowed to flip.
  • The largest such window gives the answer, since flipping that 0 (if present) gives the maximum consecutive 1s.
  • This approach only requires a single pass through the array, making it very efficient.

Example Walkthrough

Let's take the input nums = [1,0,1,1,0].

1. Start with left = 0, right = 0, zero_count = 0, max_len = 0.
2. right = 0: nums[0] = 1. No change to zero_count. Window is [0,0], length 1. max_len = 1.
3. right = 1: nums[1] = 0. zero_count = 1. Window is [0,1], length 2. max_len = 2.
4. right = 2: nums[2] = 1. zero_count = 1. Window is [0,2], length 3. max_len = 3.
5. right = 3: nums[3] = 1. zero_count = 1. Window is [0,3], length 4. max_len = 4.
6. right = 4: nums[4] = 0. zero_count = 2 (now too many zeros).
7. Move left forward: nums[0] = 1 (no effect), left = 1. nums[1] = 0, decrement zero_count = 1, left = 2. Now window is [2,4], length 3.
8. The largest window found was length 4 (from [0,3]), so the answer is 4.

This matches the intuition: flipping the first 0 at index 1 connects the first three 1s, giving [1,1,1,1,0] or [1,0,1,1,1] (if you flip the last 0), both giving four consecutive 1s.

Code Implementation

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        left = 0
        zero_count = 0
        max_len = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len
      

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0, zero_count = 0, max_len = 0;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0)
                ++zero_count;
            while (zero_count > 1) {
                if (nums[left] == 0)
                    --zero_count;
                ++left;
            }
            max_len = max(max_len, right - left + 1);
        }
        return max_len;
    }
};
      

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0, zeroCount = 0, maxLen = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeroCount++;
            while (zeroCount > 1) {
                if (nums[left] == 0) zeroCount--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}
      

function findMaxConsecutiveOnes(nums) {
    let left = 0, zeroCount = 0, maxLen = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeroCount++;
        while (zeroCount > 1) {
            if (nums[left] === 0) zeroCount--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}
      

Time and Space Complexity

• Brute-force Approach: For each 0 in the array (up to n), flip and scan the entire array for the longest sequence of 1s. This is O(n^2) time and O(1) space.
• Optimized Sliding Window: We scan each element at most twice (once as right, once as left), so the time complexity is O(n). Space complexity is O(1) since we use only a few variables.

The sliding window approach is thus highly efficient and suitable for large arrays.

Summary

In summary, the Max Consecutive Ones II problem can be solved efficiently using a sliding window approach. By maintaining a window with at most one 0, we can find the largest possible sequence of consecutive 1s after flipping at most one 0. This method avoids unnecessary repeated scans and gives a clear, elegant, and optimal solution to the problem.