Problem Description

You are given a binary array nums that contains only 0s and 1s. You need to find the maximum number of consecutive 1s that you can get if you are allowed to flip at most one 0 to 1.

For example, if you have the array [1, 0, 1, 1, 0], you can flip the first 0 to get [1, 1, 1, 1, 0], which gives you 4 consecutive 1s. Or you could flip the last 0 to get [1, 0, 1, 1, 1], which gives you 3 consecutive 1s. The maximum would be 4.

The key constraint is that you can flip at most one 0, meaning you can either flip exactly one 0 or flip no 0s at all. Your goal is to find the longest possible sequence of consecutive 1s after performing this operation optimally.

Intuition

The problem essentially asks us to find the longest subarray that contains at most one 0. We can think of this as a sliding window problem where we maintain a window that satisfies our constraint.

The key insight is that we're looking for a contiguous subarray (window) where we have at most one 0. As we expand our window by moving through the array, we keep track of how many 0s are in our current window. When we encounter more than one 0, we need to shrink our window from the left until we're back to having at most one 0.

What makes this solution elegant is the observation that we don't actually need to shrink the window in the traditional sense. Since we're looking for the maximum length, once we've found a window of a certain size, we never need to consider smaller windows. So instead of shrinking the window when we have too many 0s, we can just slide it forward by moving both left and right boundaries together.

Think of it like this: if we've already found a valid window of size 5, there's no point in looking at windows of size 4 or smaller. So when we encounter a violation (more than one 0), we just shift the entire window forward by one position. This maintains the window size while exploring new possibilities. The window will only grow when we find a longer valid sequence.

The expression x ^ 1 is used to flip bits: if x is 1, x ^ 1 gives 0; if x is 0, x ^ 1 gives 1. So cnt += x ^ 1 increments the counter when we see a 0, and cnt -= nums[l] ^ 1 decrements it when we remove a 0 from the left of the window.

Solution Approach

We use a sliding window technique with a two-pointer approach. The algorithm maintains a window that contains at most one 0.

Here's how the implementation works:

1. Initialize variables: We set l = 0 as the left boundary of our window and cnt = 0 to track the number of 0s in our current window.

2. Iterate through the array: For each element x in nums:

   • We use cnt += x ^ 1 to update our 0 count. The XOR operation x ^ 1 flips the bit: if x is 0, it becomes 1 (incrementing our count), and if x is 1, it becomes 0 (no increment).

3. Handle window constraint: When cnt > 1 (more than one 0 in the window):

   • We move the left boundary right by one position: l += 1
   • We update the count by removing the contribution of the element that just left the window: cnt -= nums[l] ^ 1
   • This effectively slides the window forward while maintaining its size

4. Calculate result: The final answer is len(nums) - l, which represents the size of the largest valid window we found.

The key optimization here is that we don't shrink the window when we encounter a violation. Instead, we slide it forward maintaining its current size. This works because:

• If we have a valid window of size k, we're not interested in smaller windows
• The window only grows when we can extend it without violating the constraint
• By the end, l tells us how much we had to shift from the beginning, so len(nums) - l gives us the maximum window size

This approach runs in O(n) time with O(1) space, making it very efficient.

Example Walkthrough

Let's walk through the algorithm with the array nums = [1, 0, 1, 1, 0].

Initial State:

• l = 0 (left boundary)
• cnt = 0 (count of zeros in window)
• Window: empty

Step 1: Process index 0, value = 1

• cnt += 1 ^ 1 = 0 (no increment since it's a 1)
• cnt = 0 (still ≤ 1, so window is valid)
• Window: [1], from index 0 to 0

Step 2: Process index 1, value = 0

• cnt += 0 ^ 1 = 1 (increment since it's a 0)
• cnt = 1 (still ≤ 1, so window is valid)
• Window: [1, 0], from index 0 to 1

Step 3: Process index 2, value = 1

• cnt += 1 ^ 1 = 0 (no increment since it's a 1)
• cnt = 1 (still ≤ 1, so window is valid)
• Window: [1, 0, 1], from index 0 to 2

Step 4: Process index 3, value = 1

• cnt += 1 ^ 1 = 0 (no increment since it's a 1)
• cnt = 1 (still ≤ 1, so window is valid)
• Window: [1, 0, 1, 1], from index 0 to 3

Step 5: Process index 4, value = 0

• cnt += 0 ^ 1 = 1 (increment since it's a 0)
• cnt = 2 (now > 1, need to adjust!)
• Since cnt > 1, we slide the window:
  • cnt -= nums[0] ^ 1 = nums[0] ^ 1 = 1 ^ 1 = 0 (remove contribution of nums[0])
  • l = 1 (move left boundary)
  • cnt = 2 (still > 1, need another adjustment!)
• Since cnt > 1 again:
  • cnt -= nums[1] ^ 1 = nums[1] ^ 1 = 0 ^ 1 = 1 (remove contribution of nums[1])
  • l = 2 (move left boundary)
  • cnt = 1 (now valid)
• Window: [1, 1, 0], from index 2 to 4

Final Result:

• l = 2
• Maximum length = len(nums) - l = 5 - 2 = 3

Wait, this gives us 3, but we should get 4. Let me reconsider the algorithm logic.

Actually, I need to correct my understanding. The algorithm slides the window by exactly one position when we exceed the constraint:

Step 5 Corrected: Process index 4, value = 0

• cnt += 0 ^ 1 = 1 (increment since it's a 0)
• cnt = 2 (now > 1, need to adjust!)
• Since cnt > 1:
  • cnt -= nums[l] ^ 1 = nums[0] ^ 1 = 1 ^ 1 = 0 (no decrement, nums[0] was a 1)
  • l += 1 (move left boundary from 0 to 1)
  • cnt remains 2 (still > 1)
• Since cnt > 1 still:
  • cnt -= nums[l] ^ 1 = nums[1] ^ 1 = 0 ^ 1 = 1 (decrement, nums[1] was a 0)
  • l += 1 (move left boundary from 1 to 2)
  • cnt = 1 (now valid)

Actually, let me reconsider the algorithm flow. The adjustment happens within the loop iteration:

Step 5 Refined: Process index 4, value = 0

• cnt += 0 ^ 1 = 1 (increment since it's a 0)
• cnt = 2 (now > 1)
• While cnt > 1:
  • cnt -= nums[l] ^ 1 = nums[0] ^ 1 = 1 ^ 1 = 0
  • l = 1
  • cnt is still 2, so continue
  • cnt -= nums[l] ^ 1 = nums[1] ^ 1 = 0 ^ 1 = 1
  • l = 2
  • cnt = 1 (now valid, exit while loop)

Actually, reviewing the original solution more carefully, it seems the adjustment only happens once per iteration. Let me trace through more carefully:

Correct Walkthrough:

The key is that when cnt > 1, we slide the window forward by one position only.

• i=0: x=1, cnt = 0, window=[1]
• i=1: x=0, cnt = 1, window=[1,0]
• i=2: x=1, cnt = 1, window=[1,0,1]
• i=3: x=1, cnt = 1, window=[1,0,1,1]
• i=4: x=0, cnt = 2 (too many zeros!)
  • Slide window: cnt -= nums[0]^1 = 0, l = 1
  • Now cnt = 2, but we only slide once per iteration
  • Window effectively becomes [0,1,1,0]

The final answer is 5 - 1 = 4, which matches our expected result. The window [0,1,1,0] can have its 0 flipped to get [1,1,1,1], giving us 4 consecutive 1s.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once with a single for loop. Although there's a while-loop-like behavior with the sliding window (when cnt > 1), each element is processed at most twice - once when the right pointer encounters it and at most once when the left pointer moves past it. This maintains a linear time complexity.

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for the variables l (left pointer) and cnt (counter), regardless of the input size. No additional data structures that scale with the input are created.

Common Pitfalls

Pitfall 1: Misunderstanding the Window Sliding Logic

Many people initially think the algorithm shrinks the window when encountering a violation (more than one 0), but it actually maintains the window size and slides it forward. This can lead to confusion about why we return len(nums) - left instead of tracking the maximum window size explicitly.

Why this happens: The code appears to only move left by 1 when we have too many zeros, which seems like it's not properly shrinking the window to become valid again.

Solution: Understand that this is an optimization. Once we achieve a window of size k, we're only interested in finding larger windows. By sliding (not shrinking) the window, we maintain the best size found so far. The final position of left tells us how much we've shifted from the start, giving us the maximum window size.

Pitfall 2: Incorrect Handling of All-1s Arrays

When the array contains only 1s (no zeros to flip), some might think special handling is needed or that the algorithm won't work correctly.

Example: For [1, 1, 1, 1], some might worry the algorithm won't account for the case where no flip is needed.

Solution: The algorithm handles this naturally. When there are no zeros, zero_count never exceeds 1, so left stays at 0, and we correctly return len(nums) - 0 = len(nums).

Pitfall 3: Off-by-One Error in Manual Implementation

When implementing this from scratch, a common mistake is updating the zero count before moving the left pointer:

# Incorrect order
if zero_count > 1:
    left += 1
    zero_count -= nums[left] ^ 1  # Bug: using new left position

Solution: Always remove the element at the current left position from the count before incrementing left:

# Correct order
if zero_count > 1:
    zero_count -= nums[left] ^ 1  # Use current left position
    left += 1

Pitfall 4: Overcomplicating with Maximum Tracking

Some solutions unnecessarily track the maximum window size explicitly:

# Overcomplicated
max_length = 0
for right in range(len(nums)):
    # ... window logic ...
    max_length = max(max_length, right - left + 1)
return max_length

Solution: The optimized approach eliminates this by recognizing that the window only grows or maintains its size, never truly shrinks, so the final window size is the maximum.