Max Consecutive Ones Iii - Leetcode Solution

Problem Statement:

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example:

Input: A = [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]

The longest subarray with only 1s has length 6.

Solution:

The problem is that we need to find the maximum length (contiguous) subarray that contains only 1s after changing at most K values from 0 to 1.

• Traverse through the array and keep track of the number of zeros we have seen so far.
• If the number of zeros is less than or equal to K, we can continue to increase the length of the subarray.
• If we see more than K zeros, we need to decrease the length of the subarray by removing the leftmost zero, keeping track of the number of zeros removed.
• We continue to move the left pointer until we have removed at most K zeros and increase the length of the subarray.

At each step, we keep track of the length of the subarray and return the maximum length seen so far.

Pseudo code:

left = 0 zeros = 0 max_length = 0 for right in range(len(A)): if A[right] == 0: zeros += 1 while zeros > K: if A[left] == 0: zeros -= 1 left += 1 max_length = max(max_length, right - left + 1) return max_length

Explanation:

We initialize left pointer to 0, zeros to 0 and max_length to 0.

We loop through the array A, incrementing the right pointer and checking if the element at A[right] is a 0, we increment the zeros count.

If the number of zeros is greater than K, this means that we need to remove zeros from the left of the array until the count of zeros is less than or equal to K.

We do this using a while loop. While the count of zeros is greater than K, we increment the left pointer, and if the element at A[left] is a 0, we decrement the zeros count.

Once zeros count is less than or equal to K, we have a valid subarray. We obtain the length of the subarray by subtracting left from right and adding 1.

We check to see if the new length is greater than the current max_length. If it is, update max_length.

Finally, we return max_length which represents the length of the longest subarray with at most K 0s flipped to 1s.

Time Complexity:

We traverse the array only once. Therefore the time complexity of the algorithm is O(N), where N is the length of the array.

Space Complexity:

We use constant extra space to store the variables zeros, left and max_length. Therefore the space complexity of the algorithm is O(1).

Overall, the solution is efficient and optimal, providing the answer in O(N) time.

1