Sliding Window

Longest Subarray with Ones after Replacement (Max Consecutive Ones after replacement)

Rajeev SinghAlgorithms1 mins read

Longest Subarray with Ones after Replacement (Max Consecutive Ones)

Problem Statement

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

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]

Example 2:

Input: A = [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
Output: 9
Explanation: Replace the 0s at index 6, 9, and 10 with 1s to get the longest contiguous subarray of 1s.

Solution in Java

This problem is a variation of the problem Longest Substring with Same Letters after Replacement. We can solve it using a similar sliding window strategy discussed in the previous problem.

This problem can be solved using the sliding window pattern.

  • Initialize two variables: windowStart = 0 and windowEnd = 0. These define the lower and upper bounds of the sliding window. So we start with an initial window size of 1.
  • Initialize a variable numReplacements to keep track of the number of replacements done from 0 to 1.
  • Iterate over the array until the windowEnd index reaches the end of the array.
    • If a[windowEnd] == 0, then we need to flip this element to 1 to obtain a contiguous subarray of 1s. Therefore, we increment numReplacements.
    • If numReplacements is greater than the number of allowed replacements, then we can’t proceed, and we must shift our window by incrementing windowStart until numReplacements becomes equal to the number of allowed replacements.
    • 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.
import java.util.Scanner;

class LongestSubarrayWithOnesAfterReplacement {
  private static int findMaxConsecutiveOnes(int[] a, int k) {
      int maxOnes = Integer.MIN_VALUE;
      int numReplacements = 0;
      int windowStart = 0;
      
      for(int windowEnd = 0; windowEnd < a.length; windowEnd++) {   
          if(a[windowEnd] == 0) {
              numReplacements++;    
          }
          
          while(numReplacements > k) {
              if(a[windowStart] == 0) {
                  numReplacements--;
              }
              windowStart++;
          }
          
          maxOnes = Math.max(maxOnes, windowEnd-windowStart+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 after replacement = %d%n", result);
  }
}
# Output
Length of longest contiguous subarray containing only 1s after replacement = 6