Max Consecutive Ones III

LeetCode Q 1004 - Max Consecutive Ones III

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.

Example 1:
Input: A = [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: A = [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.

Note:

• 1 <= A.length <= 20000
• 0 <= K <= A.length
• A[i] is 0 or 1

Solution : Sliding Window

This problem is similar to Longest Repeating Character Replacement.

Without constraints, maximum consecutive Ones length is
length of array
With constraints, then it becomes
length of array - number of 1s in the array <= k

Code:

public int longestOnes(int[] A, int K) {
	
	if (A.length <= K) return A.length;
	
	int[] count = new int[2];
	
	int start = 0, end = 0, maxCount = 0, res = 0;
	while (end < A.length) {
		count[A[end]]++;
		while (end - start + 1 - count[1] > K) {
			count[A[start++]]--;
		}
		maxCount = Math.max(maxCount, end - start + 1);
		end++;
	}
	
	return maxCount;
}