# Leetcode 1004 - Max Consecutive Ones III

### Understanding the problem

Given an array A of 0s and 1s, we are to find the maximum number of consecutive 1s in the array A after flipping at most one 0.

``````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.
``````

### Grow Your Tech Career. Meet Expert coaches from top companies

Meet A MAANG Coach

We can use the sliding window approach to solve this problem.

1. Initialize two pointers i and j to the start of the array and a variable max_len to keep track of the maximum number of consecutive 1s seen so far.
2. Iterate through the array with pointer j and check if the current element is 0, decrement the number of allowed flips.
3. If the number of allowed flips is less than 0, increment the left pointer i and check if the leftmost element of the window is a 0. If it is, increment the number of allowed flips.
4. Keep updating the max_len variable with the maximum size of the window seen so far, which is (j - i + 1).
5. Return the max_len variable as the result after the iteration.

This approach is a variant of the sliding window algorithm, where we use a while loop to move the left pointer i until we have flipped at most one 0, and keep track of the maximum size of the window seen so far.

``````def longestOnes(A: List[int], K: int) -> int:
i = 0
max_len = 0
for j in range(len(A)):
if A[j] == 0:
K -= 1
while K < 0:
if A[i] == 0:
K += 1
i += 1
max_len = max(max_len, j - i + 1)
return max_len
``````

``````assert longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2) == 6
assert longestOnes([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3) == 10
``````

The above test cases passed, it gives the correct answer.

In this problem, we are able to find the maximum number of consecutive 1s in the array A after flipping at most one 0 by using the sliding window approach. The time complexity of this solution is O(n) and the space complexity is O(1).

### Grow Your Tech Career. Meet Expert coaches from top companies

Meet A MAANG Coach