Technical Interview Question:

You are given an array of 0s and 1s, and an integer k. Your task is to find the maximum number of consecutive 1s by flipping at most k 0s.

Write a function max_consecutive_ones(nums: List[int], k: int) -> int to solve the problem. The function should return an integer representing the maximum number of consecutive 1s.

Example:

Input:

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

Output:

4

Explanation:

By flipping at most 2 zeros, we can obtain the longest continuous subarray of 1s, which contains 1, 1, 0, 0, 1. Therefore, the maximum number of consecutive 1s is 4.

Answer:

from typing import List

def max_consecutive_ones(nums: List[int], k: int) -> int:
    # Initialize two pointers left and right at the start of the array
    left = right = 0
    zeros_count = 0
    max_ones = 0
    
    # Loop through the array using right pointer
    while right < len(nums):
        # If the current number is 0, increment the count of zeros
        if nums[right] == 0:
            zeros_count += 1
        
        # If the number of zeros exceeds k, we need to move the left pointer
        while zeros_count > k:
            # If the number at left pointer is 0, decrement the count of zeros
            if nums[left] == 0:
                zeros_count -= 1
            left += 1
        
        # Update the maximum number of consecutive ones
        max_ones = max(max_ones, right - left + 1)
        right += 1
    
    return max_ones

The code above uses the sliding window technique to solve the problem. Here is a step-by-step explanation of the solution:

1. Initialize two pointers left and right at the start of the array, a variable zeros_count to keep track of the number of zeros, and a variable max_ones to store the maximum number of consecutive ones.
2. Loop through the array using the right pointer.
3. If the current number is 0, increment the count of zeros.
4. If the number of zeros exceeds k, we need to move the left pointer to maintain at most k zeros in the window. If the number at the left pointer is 0, decrement the count of zeros. Increment the left pointer.
5. Update the maximum number of consecutive ones by calculating the window size right - left + 1 and taking the maximum with the current max_ones value.
6. Increment the right pointer to expand the window.
7. Repeat steps 3-6 until we reach the end of the array.
8. Return the max_ones variable.

The time complexity of this solution is O(n), where n is the length of the input array nums. The space complexity is O(1), as we are using a constant amount of extra space.