Problem Statement

Given a binary array nums containing only 0 and 1 and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Examples

Example 1:

• Input: nums = [1, 0, 0, 1, 1, 0, 1, 1], k = 2
• Expected Output: 6
• Justification: By flipping 0 at the second and fifth index in the list, we get [1, 0, 1, 1, 1, 1, 1, 1], which has 6 consecutive 1s.

Example 2:

• Input: nums = [1, 0, 1, 1, 0, 0, 1, 1], k = 1
• Expected Output: 4
• Justification: By flipping 0 at 1st index, we get [1, 1, 1, 1, 0, 1, 1, 1], with a maximum of 4 consecutive 1s.

Example 3:

• Input: nums = [1, 0, 0, 1, 1, 0, 1], k = 3
• Expected Output: 7
• Justification: By flipping all three zeros, we get [1, 1, 1, 1, 1, 1, 1], which has 7 consecutive 1s.

Constraints:

• 1 <= nums.length <= 10⁵
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

Solution

To solve this problem, we'll use a sliding window approach. We'll keep a window of 1s that we expand as long as the number of 0s within the window doesn't exceed k. If the number of 0s exceeds k, we'll move the start of the window forward to reduce the number of 0s. This approach ensures that we always have the longest possible window of 1s by changing at most k 0s to 1s.

This approach works effectively because it processes each element in the list once, ensuring that the algorithm runs in linear time. By keeping track of the count of 0s within the current window, we can dynamically adjust the window size to maximize the sequence of consecutive 1s.

Step-by-step Algorithm

1. Initialization:

   • Initialize two pointers left and right to 0.
   • Initialize max_length to 0 to keep track of the maximum length of consecutive 1s found.
   • Initialize zero_count to 0 to keep track of the number of 0s in the current window.

2. Expand the window:

   • While right is less than the length of the list nums:
     • If the element at nums[right] is 0, increment zero_count by 1.
     • While zero_count exceeds k (i.e., more than k 0s in the current window):
       • If the element at nums[left] is 0, decrement zero_count by 1.
       • Move the left pointer to the right by 1.
     • Update max_length to be the maximum of its current value and the length of the current window (right - left + 1).
     • Move the right pointer to the right by 1.

3. Return the result:

   • After the loop ends, return max_length as the result.

Algorithm Walkthrough

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

1. Initialization:

   • left = 0
   • right = 0
   • max_length = 0
   • zero_count = 0

2. First Iteration (right = 0):

   • nums[0] is 1.
   • zero_count remains 0.
   • max_length is updated to 1 (window: [1]).
   • Increment right to 1.

3. Second Iteration (right = 1):

   • nums[1] is 0.
   • Increment zero_count to 1.
   • max_length is updated to 2 (window: [1, 0]).
   • Increment right to 2.

4. Third Iteration (right = 2):

   • nums[2] is 0.
   • Increment zero_count to 2.
   • max_length is updated to 3 (window: [1, 0, 0]).
   • Increment right to 3.

5. Fourth Iteration (right = 3):

   • nums[3] is 1.
   • zero_count remains 2.
   • max_length is updated to 4 (window: [1, 0, 0, 1]).
   • Increment right to 4.

6. Fifth Iteration (right = 4):

   • nums[4] is 1.
   • zero_count remains 2.
   • max_length is updated to 5 (window: [1, 0, 0, 1, 1]).
   • Increment right to 5.

7. Sixth Iteration (right = 5):

   • nums[5] is 0.
   • Increment zero_count to 3.
   • zero_count exceeds k, so start adjusting left:
     • nums[0] is 1, zero_count remains 3, increment left to 1.
     • nums[1] is 0, decrement zero_count to 2, increment left to 2.
   • max_length remains 5 (window: [0, 1, 1, 0]).
   • Increment right to 6.

8. Seventh Iteration (right = 6):

   • nums[6] is 1.
   • zero_count remains 2.
   • max_length is updated to 5 (window: [0, 1, 1, 0, 1]).
   • Increment right to 7.

9. Eighth Iteration (right = 7):

   • nums[7] is 1.
   • zero_count remains 2.
   • max_length is updated to 6 (window: [0, 1, 1, 0, 1, 1]).
   • Increment right to 8, which ends the loop as right equals the length of nums.

10. Return Result:

    • The final value of max_length is 6.