Naive Approach: Brute Force

We can iterate through all possible subarrays and, for each subarray, count the number of zeros. If the number of zeros is less than or equal to k, we update the maximum length found so far. This approach is straightforward but inefficient.

Code (Python):

def longest_ones_brute_force(nums, k):
    max_len = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subarray = nums[i:j+1]
            zeros = subarray.count(0)
            if zeros <= k:
                max_len = max(max_len, len(subarray))
    return max_len

Time Complexity: O(n^3), where n is the length of the input array. This is because we have nested loops to generate all subarrays (O(n^2)), and for each subarray, we count the zeros (O(n)).

Space Complexity: O(1), excluding the space used by the input array.

Optimal Approach: Sliding Window

A more efficient approach is to use the sliding window technique. We maintain a window and expand it to the right. If the number of zeros in the window exceeds k, we shrink the window from the left until the number of zeros is back within the limit. The maximum window size encountered during this process is the answer.

Algorithm:

1. Initialize two pointers, left and right, to 0.
2. Initialize a variable zeros to keep track of the number of zeros in the current window.
3. Iterate through the array with the right pointer.
4. If nums[right] is 0, increment zeros.
5. While zeros is greater than k, increment the left pointer. If nums[left] is 0, decrement zeros.
6. Update the maximum length of the window.
7. Return the maximum length.

Code (Python):

def longest_ones_sliding_window(nums, k):
    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

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once with the right pointer, and the left pointer can only move up to n times in the worst case.

Space Complexity: O(1), as we only use a constant amount of extra space.

Edge Cases

• Empty array: If the input array is empty, return 0.
• k = 0: If k is 0, return the length of the longest consecutive 1s.
• k >= length of array: If k is greater than or equal to the length of the array, return the length of the array.
• Array with all 1s: If the array consists only of 1s, return the length of the array.

Example

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

1. left = 0, right = 0, zeros = 0, max_len = 0
2. Iterate right:
   • right = 0, nums[0] = 1, zeros = 0, max_len = 1
   • right = 1, nums[1] = 1, zeros = 0, max_len = 2
   • right = 2, nums[2] = 1, zeros = 0, max_len = 3
   • right = 3, nums[3] = 0, zeros = 1, max_len = 4
   • right = 4, nums[4] = 0, zeros = 2, max_len = 5
   • right = 5, nums[5] = 0, zeros = 3
   • zeros > k, so increment left:
     • left = 0, nums[0] = 1
     • left = 1, nums[1] = 1
     • left = 2, nums[2] = 1
     • left = 3, nums[3] = 0, zeros = 2, left = 4
   • right = 6, nums[6] = 1, zeros = 2, max_len = 6
   • right = 7, nums[7] = 1, zeros = 2, max_len = 6
   • right = 8, nums[8] = 1, zeros = 2, max_len = 6
   • right = 9, nums[9] = 1, zeros = 2, max_len = 6
   • right = 10, nums[10] = 0, zeros = 3
   • zeros > k, so increment left:
     • left = 4, nums[4] = 0, zeros = 2, left = 5
   • max_len = 6

Return 6.