Max Consecutive Ones III

Sliding Window

Problem

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.

For example:

Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1]
k=2

Output: 6

Explanation: Replace the '0' at index 5 and 8 to 
have the longest contiguous subarray of 1s 
having length 6.

Input: 
Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], 
k=3

Output: 9

Explanation: Replace the '0' at index 6, 9, and 
10 to have the longest contiguous subarray of 1s
having length 9.

Thought Process

• It is a similar approach to Longest Repeating Character Replacement

• Following a similar approach, we'll iterate through the array to add one number at a time in the window. We'll also keep track of the maximum number of repeating 1s in the current window (maxOnesCount). So at any time, we know that we can have a window with 1s repeating 'maxOnesCount' times, so we should try to replace the remaining 0s. If we have more thank 'k' remaining 0s, we should shrink the window as we are not allowed to replace more than 'k' 0s.

Solution

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        onesCount = 0
        maxLen = 0
        start = 0
        
        for i in range(len(A)):
            if A[i] == 1:
                onesCount+=1
            
            if (i - start + 1 - onesCount) > K:
                if A[start] == 1:
                    onesCount-=1
                start+=1
            
            maxLen = max(maxLen, i - start + 1)
            
        return maxLen

Key Points

• Keeping count of maximum number of 1s within the window and applying the approach we usedin Longest Repeating Character Replacement

• We're finding the number of zeroes we have within our window to see if that number is greater than 'K'. If so, we need to shrink our window.

Time Complexity

• Time: $O(n)$

• Space: $O(1)$