We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Max Consecutive Ones III

Difficulty: Medium

Problem Description

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Key Insights

  • The problem can be efficiently solved using the sliding window technique.
  • Maintain a window that counts the number of 0s within it and ensures it does not exceed k.
  • Adjust the window's left boundary when the count of 0s exceeds k to maximize the length of the window.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will use a sliding window approach. We will maintain two pointers (left and right) that represent the current window's boundaries. As we increment the right pointer to expand the window, we count the number of 0s within the window. If the count exceeds k, we will increment the left pointer to shrink the window until we are back within the limit of k 0s. Throughout this process, we will keep track of the maximum length of the window that satisfies the condition.

Code Solutions

def longest_ones(nums, k):
    left = 0
    max_length = 0
    zero_count = 0
    
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1
        
        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1
        
        max_length = max(max_length, right - left + 1)
    
    return max_length
← Back to All Questions