Max Consecutive Ones III

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

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        zeros = 0
        max_len = 0

        for right in range(len(nums)):
            if nums[right] == 0:
                zeros += 1

            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1

            max_len = max(max_len, right - left + 1)

        return max_len

Brute Force Solution

The brute force solution would involve iterating through all possible subarrays and, for each subarray, counting the number of zeros. If the number of zeros is less than or equal to k, we update the maximum length. This is highly inefficient.

Optimal Solution

The optimal solution uses a sliding window approach. We maintain a window and track the number of zeros within the window. If the number of zeros exceeds k, we shrink the window from the left until the number of zeros is back within the limit.

Big(O) Run-time Analysis

The run-time complexity is O(n), where n is the length of the input array nums. The for loop iterates through the array once, and the while loop inside it runs at most n times in total (as left can only increment up to n).

Big(O) Space Usage Analysis

The space complexity is O(1) because we only use a few constant extra variables (left, zeros, max_len). The algorithm operates in place without using additional data structures that scale with the input size.

Edge Cases

1. Empty Array: If the input array nums is empty, the function should return 0.
2. k = 0: If k is 0, the function should return the maximum number of consecutive 1s in the array without flipping any zeros.
3. k >= length of nums: If k is greater than or equal to the length of nums, the function should return the length of nums because we can flip all zeros to ones.
4. All 1s: If the array contains all 1s, the function should return the length of the array.
5. All 0s: If the array contains all 0s, the function should return k (or the length of the array, whichever is smaller).