Sliding window
Longest Subarray with Ones after Replacement
The problem presents a binary array nums, comprised of 0s and 1s. The task is to find the size of the largest contiguous subarray of 1s that could be obtained by removing exactly one element from the array. You are also informed that if there is no such subarray made up entirely of 1s after removing an element, the function should return 0.
Input:
nums = [1, 1, 0, 1, 1, 1, 0, 1, 1]
Explanation
- After removing the
0at index 2, the longest contiguous subarray of1s is[1, 1, 1, 1, 1], which is of length5. - This is the maximum length we can achieve by removing exactly one element from the given array.
public int longestSubarray(int[] nums) {
int left = 0; // Left pointer for the sliding window
int zeroCount = 0; // To count the number of zeros in the current window
int maxLength = 0; // To store the maximum length of the subarray of 1's
for (int right = 0; right < nums.length; right++) {
// If we encounter a zero, increase the zero count
if (nums[right] == 0) {
zeroCount++;
}
// If zeroCount becomes more than 1, shrink the window from the left
while (zeroCount > 1) {
if (nums[left] == 0) {
zeroCount--;
}
left++;
}
// Calculate the maximum length of the window containing at most one zero
maxLength = Math.max(maxLength, right - left);
}
// Return maxLength as the result
return maxLength;
}
