Max Consecutive ones III

1004.Max Consecutive Ones III

Array

Sliding Window

Two Pointers

Problem Statement:

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.

Example:

Input:

nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

→

Output:

6

Java Solution:

// Easy sliding window - sliding window "contains all ones"
// It works because we don't ACTUALLY modify the array so we can "shorten"
public int longestOnes(int[] A, int k) {
    int max = 0;  // Keeps track of the maximum length of the subarray with at most k flips
    int i = 0;    // Start of the sliding window (left pointer)
    int j = 0;    // End of the sliding window (right pointer)

    // Iterate over the array
    while (j < A.length) {
        
        if (A[j] == 0) k--;  // Use one of the allowed flips if A[j] is 0

        // If k < 0, we need to shrink the window from the left
        while (k < 0) {
            // THIS WORKS BECAUE YOU NEVER ACTUALLY MODIFIED THE ARRAY!!
            if (A[i] == 0) k++;  // Undo a flip when moving the left pointer past a 0
            i++;  // Move the left pointer forward
        }

        // Calculate the size of the current valid window and update max
        max = Math.max(max, j - i + 1);

        j++;  // Move the right pointer forward to expand the window
    }

    return max;  // Return the maximum length of the subarray found
}

Python Solution:

def longestOnes(self, A: List[int], k: int) -> int:
    max_length = i = j = 0
    
    while j < len(A):
        if A[j] == 0:
            k -= 1
            
        while k < 0:
            if A[i] == 0:
                k += 1
            i += 1
            
        max_length = max(max_length, j - i + 1)
        j += 1
        
    return max_length

C++ Solution:

class Solution {
public:
    int longestOnes(vector<int>& A, int k) {
        int max_length = 0;
        int i = 0;
        
        for(int j = 0; j < A.size(); j++) {
            if(A[j] == 0) {
                k--;
            }
            
            while(k < 0) {
                if(A[i] == 0) {
                    k++;
                }
                i++;
            }
            
            max_length = max(max_length, j - i + 1);
        }
        
        return max_length;
    }
};

Complexity:

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