1.7 Longest Subarray with Ones after Replacement (hard)

Problem:

Max Consecutive Ones III

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 1:

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.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Solution:

public int longestOnes(int[] A, int K) {
    int max = 0;
    int zeroCount = 0; // zero count in current window
    int i = 0; // slow pointer
    for(int j = 0; j < A.length; ++j) {
        if(A[j] == 0) { // move forward j, if current is 0, increase the zeroCount
            zeroCount++;
        }
        
        // when current window has more than K, the window is not valid any more
        // we need to loop the slow pointer until the current window is valid
        while(zeroCount > K) {  
            if(A[i] == 0) {
                zeroCount--;
            }
            i++;
        }
        max = Math.max(max, j-i+1); // everytime we get here, the current window is valid 
    }
    return max;
}