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.

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

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• I’ve never done a leetcode problem before in my life, but I program every single day. I was recommended this sub, and I have a question after seeing the seriousness of leetcoders.
• Two Sum and Its Variants
• Leetcode 222 - Count Complete Tree Nodes
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 340 - Longest Substring with At Most K Distinct Characters
• Leetcode 300 - Longest Increasing Subsequence
• Leetcode 930 - Binary Subarrays With Sum
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together