Longest Subarray with Ones after Replacement - Java Solution

1. Introduction

This blog post discusses a sliding window problem often encountered in array processing: finding the longest subarray containing only 1’s in a binary array, given that up to K values can be changed from 0 to 1.

Problem

Given an array A of 0's and 1's, and an integer K indicating the maximum number of 0's that can be flipped to 1's, find the length of the longest contiguous subarray that contains only 1’s after at most K replacements.

Example 1:

Input: A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2

Output: 6

Explanation: Flip the 0s at index 5 and 10 to 1s to get the longest subarray.

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.

2. Solution Steps

1. Use the sliding window technique to process the array.

2. Keep track of the number of zeros within the current window.

3. If the number of zeros exceeds K, shrink the window from the left until it contains K or fewer zeros.

4. Update the maximum length of the window as the window changes.

5. Return the maximum length found.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] A1 = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
        System.out.println("Longest subarray with ones after replacement: " + findMaxConsecutiveOnes(A1, 2));

        int[] A2 = {0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1};
        System.out.println("Longest subarray with ones after replacement: " + findMaxConsecutiveOnes(A2, 3));
    }

    // Method to find the longest subarray with ones after replacement
    public static int findMaxConsecutiveOnes(int[] A, int K) {
        int windowStart = 0, maxLength = 0, maxOnesCount = 0;

        for (int windowEnd = 0; windowEnd < A.length; windowEnd++) {
            if (A[windowEnd] == 1) {
                maxOnesCount++;
            }

            // If the number of zeros exceeds K, shrink the window
            if (windowEnd - windowStart + 1 - maxOnesCount > K) {
                if (A[windowStart] == 1) {
                    maxOnesCount--;
                }
                windowStart++;
            }

            maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
        }

        return maxLength;
    }
}

Output:

Longest subarray with ones after replacement: 6
Longest subarray with ones after replacement: 9

Explanation:

The findMaxConsecutiveOnes method applies the sliding window technique to find the longest subarray with ones after at most K replacements. It maintains a count of the number of 1's in the window and adjusts the window size when the number of 0's exceeds K. 

For example, in the array [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0] with K = 2, the longest subarray with ones after replacement is of length 6. 

The method correctly identifies and counts the length of the longest subarray fulfilling the criteria.