Problem Description

You are given a binary array nums containing only 0s and 1s, and an integer k. You can flip at most k zeros to ones. Your task is to find the maximum number of consecutive 1s you can get in the array after performing at most k flips.

For example, if nums = [1,1,0,0,1,1,0,1,1,1] and k = 2, you can flip the two 0s at positions 2 and 3 (or positions 2 and 6, or positions 3 and 6) to get consecutive 1s. The maximum consecutive 1s you can achieve is 7 by flipping the 0s at positions 2 and 6, resulting in [1,1,1,1,1,1,1,1,1,1] from index 1 to 7.

The solution uses a sliding window approach where:

• The window expands as we iterate through the array
• We track the count of 0s in the current window using cnt (calculated with XOR operation: x ^ 1 gives 1 when x is 0, and 0 when x is 1)
• When the count of 0s exceeds k, we shrink the window from the left by moving the left pointer
• The final window size represents the maximum consecutive 1s achievable

The key insight is that we don't need to shrink the window aggressively - we only move the left boundary by one position when needed, maintaining the maximum window size found so far. This is because we're interested in the maximum length, so once we find a valid window of a certain size, we never need to consider smaller windows.

Intuition

The problem essentially asks: "What's the longest subarray containing at most k zeros?" If we can find such a subarray, we know that by flipping all zeros in it to ones, we get a consecutive sequence of 1s.

This naturally leads us to think about the sliding window technique. We can maintain a window that represents a valid subarray (containing at most k zeros) and try to expand it as much as possible.

The key insight is recognizing that we're looking for the maximum length window. Once we find a valid window of size n, there's no point in considering smaller windows anymore. This means:

1. We always try to expand the window by moving the right pointer
2. When the window becomes invalid (more than k zeros), instead of shrinking it back to find the next valid window, we just slide it forward by moving both pointers

Think of it like a rubber band that can only stretch, never shrink. As we scan through the array:

• If adding a new element keeps the window valid (≤ k zeros), the window stretches
• If adding a new element makes it invalid (> k zeros), the window slides forward maintaining its size

By the end of the array traversal, the window size represents the maximum consecutive 1s we can achieve. The actual position of the window doesn't matter - we only care about its maximum size.

The XOR trick (x ^ 1) is just a clever way to count zeros: it converts 0→1 and 1→0, so cnt += x ^ 1 increments the counter when we see a 0.

Learn more about Binary Search, Prefix Sum and Sliding Window patterns.

Solution Approach

We implement a sliding window algorithm that maintains the maximum valid window size throughout the traversal:

Variables:

• l: Left pointer of the sliding window, initially at position 0
• cnt: Counter for the number of zeros in the current window
• The right pointer is implicit - it's our loop variable as we iterate through the array

Algorithm Steps:

1. Iterate through the array from left to right (this represents the right boundary of our window expanding):

   for x in nums:

2. Update zero count when we include a new element in the window:

   cnt += x ^ 1

   The XOR operation x ^ 1 returns 1 if x is 0, and 0 if x is 1, effectively counting zeros.

3. Check if window is invalid (contains more than k zeros):

   if cnt > k:

4. Slide the window forward by moving the left boundary right by one position:

   cnt -= nums[l] ^ 1  # Remove the leftmost element's contribution
   l += 1              # Move left pointer forward

   Note that we only move the left pointer by one position, not multiple. This maintains the maximum window size found so far.

5. Calculate the result:

   return len(nums) - l

   Since we've processed all elements (right pointer at the end), the window size is len(nums) - l.

Why this works:

The algorithm maintains an important invariant: the window size never decreases. When we find a valid window of size w, we never shrink below this size. If adding a new element creates an invalid window, we slide the entire window forward (move both left and right pointers by 1), keeping the size constant. This ensures that by the end, we have the maximum possible window size.

Time Complexity: O(n) - we traverse the array once
Space Complexity: O(1) - only using a few variables

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example: nums = [1,0,0,1,0,1], k = 2

We'll track the window with left pointer l, and count zeros with cnt. The right pointer moves as we iterate.

Initial state: l = 0, cnt = 0

Step 1: Process index 0 (value = 1)

• cnt += 1 ^ 1 = 0 (no zeros added)
• Window: [1], zeros count: 0 ≤ 2 ✓
• l = 0, window size = 1

Step 2: Process index 1 (value = 0)

• cnt += 0 ^ 1 = 1 (found a zero)
• Window: [1,0], zeros count: 1 ≤ 2 ✓
• l = 0, window size = 2

Step 3: Process index 2 (value = 0)

• cnt += 0 ^ 1 = 1, so cnt = 2
• Window: [1,0,0], zeros count: 2 ≤ 2 ✓
• l = 0, window size = 3

Step 4: Process index 3 (value = 1)

• cnt += 1 ^ 1 = 0
• Window: [1,0,0,1], zeros count: 2 ≤ 2 ✓
• l = 0, window size = 4

Step 5: Process index 4 (value = 0)

• cnt += 0 ^ 1 = 1, so cnt = 3
• Window would have 3 zeros > 2 ✗
• Need to slide:
  • Remove nums[0] = 1 from count: cnt -= 1 ^ 1 = 0
  • Move left: l = 1
• New window: [0,0,1,0], zeros count: 3 (still invalid!)

Step 6: Process index 5 (value = 1)

• cnt += 1 ^ 1 = 0
• Window: [0,0,1,0,1], zeros count: 3 > 2 ✗
• Need to slide:
  • Remove nums[1] = 0 from count: cnt -= 0 ^ 1 = 1, so cnt = 2
  • Move left: l = 2
• Final window: [0,1,0,1], zeros count: 2 ≤ 2 ✓

Result: len(nums) - l = 6 - 2 = 4

This means we can achieve a maximum of 4 consecutive 1s. Looking at the final window [0,1,0,1] at indices 2-5, if we flip the two zeros, we get [1,1,1,1] - indeed 4 consecutive ones!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums. The algorithm uses a single pass through the array with a for loop. Even though there's a conditional increment of the left pointer l inside the loop, each element is visited at most twice (once by the right pointer implicitly through the for loop, and potentially once when the left pointer moves). This results in a linear time complexity.

Space Complexity: O(1). The algorithm only uses a constant amount of extra space for the variables l (left pointer), cnt (count of zeros in the current window), and x (loop variable). No additional data structures that scale with the input size are used, making the space complexity constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Window Maintenance Strategy

Pitfall: Many developers initially try to aggressively shrink the window whenever it becomes invalid (contains more than k zeros), using a while loop:

# Incorrect aggressive shrinking
while zero_count > k:
    if nums[left] == 0:
        zero_count -= 1
    left += 1

This approach seems logical but actually prevents us from maintaining the maximum window size found so far. It causes the window to shrink unnecessarily, losing track of the maximum achievable length.

Solution: Use a single if statement instead of while. This maintains the window at its maximum size:

# Correct: maintain maximum window size
if zero_count > k:
    if nums[left] == 0:
        zero_count -= 1
    left += 1

2. Confusion with XOR Operation

Pitfall: Using x ^ 1 might be confusing and error-prone. Developers might mistakenly think it counts 1s instead of 0s, or forget how XOR works with binary values.

Solution: Use explicit comparison for clarity:

# Instead of: zero_count += nums[right] ^ 1
# Use this for better readability:
if nums[right] == 0:
    zero_count += 1

3. Incorrect Final Result Calculation

Pitfall: Returning right - left + 1 at the end of the loop, thinking we need to calculate the window size using both pointers:

# Incorrect if using range-based loop
for right in range(len(nums)):
    # ... window logic ...
return right - left + 1  # Wrong! right is len(nums)-1 at the end

Solution: Remember that after the loop completes, the window extends from left to the end of the array. The correct calculation is:

return len(nums) - left

4. Off-by-One Errors with Index Management

Pitfall: Mixing up whether to increment the left pointer before or after updating the zero count, leading to incorrect window management:

# Wrong order - incrementing before updating count
if zero_count > k:
    left += 1  # Wrong: should update count first
    if nums[left] == 0:  # This now checks the wrong element
        zero_count -= 1

Solution: Always update the count for the element being removed BEFORE moving the pointer:

if zero_count > k:
    if nums[left] == 0:  # Check element at current left position
        zero_count -= 1
    left += 1  # Then move the pointer