Leetcode 1004 - Max Consecutive Ones III

post-thumb

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

Plan your solution

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.

Implement your solution

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

Test your solution

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

comments powered by Disqus