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 and right = 0.
• Initialize a variable numConversions to keep track of the number of conversions done from 0 to 1.
• 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 to 1 to obtain a contiguous subarray of 1s. Therefore, we increment the numConversions value.
  • If numConversions is greater than the number of allowed conversions, then we can’t proceed, and we must shift our window by incrementing left index until numConversions 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.

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