Max Consecutive Ones III
Max Consecutive Ones III
Given an array A of 0's
and 1's
, and a value K which indicates that you may change up to K values from 0 to 1.
Return the length of the longest (contiguous) subarray that contains only 1’s.
Example:
Input: A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
Output: 6
To obtain the longest contiguous subarray of 1s, you can flip the 0s at index 5 and 10 to 1s:
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
Max Consecutive Ones III solution in Java
This problem can be solved using the two pointer sliding window technique.
- Initialize two pointers (indexes):
left = 0
andright = 0
. - Initialize a variable
numConversions
to keep track of the number of conversions done from0
to1
. - Iterate over the array until the
right
index reaches the end of the array.- If
a[right] == 0
, then we need to flip this element to1
to obtain a contiguous subarray of 1s. Therefore, we increment thenumConversions
value. - If
numConversions
is greater than the number of allowed conversions, then we can’t proceed, and we must shift our window by incrementingleft
index untilnumConversions
becomes equal to the number of allowed conversions. - In every iteration, we check if the current length of longest contiguous subarray of 1s is greater than the previous value, and we set the longest length accordingly.
- If
class MaxConsecutiveOnesIII {
private static int findMaxConsecutiveOnes(int[] a, int k) {
int maxOnes = Integer.MIN_VALUE;
int numConversions = 0;
int left = 0, right = 0;
for(right = 0; right < a.length; right++) {
if(a[right] == 0) {
numConversions++;
}
while(numConversions > k) {
if(a[left] == 0) {
numConversions--;
}
left++;
}
maxOnes = Math.max(maxOnes, right-left+1);
}
return maxOnes;
}
public static void main(String[] args) {
int[] a = new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
int k = 2;
int result = findMaxConsecutiveOnes(a, k);
System.out.printf("Length of longest contiguous subarray containing only 1s = %d", result);
}
}
# Output
Length of longest contiguous subarray containing only 1s = 6