1s that can remain after deleting exactly one element.
Problem
Given a binary array nums, delete exactly one element from the array and return the length of the longest non-empty subarray containing only1s. The deleted element can be either
0 or 1. Therefore, a valid window can contain at most one 0, which will be deleted.
Example(s)
Consider the following example(s) to understand the expected input and output.Example 1
Input
nums = [1,1,0,1]Output
3Example 2
Input
nums = [1,1,1]Output
2Solution
This solution uses the Sliding Window technique. We maintain a window containing at most one0. The right pointer expands the window, while the left pointer moves forward whenever the window contains more than one 0. For every valid window, we can delete one element. Therefore, the number of
1s remaining after the deletion is the window length minus one. We update the maximum result using
right - left, which is equivalent to the window length minus one.
class Solution {
public int longestSubarray(int[] nums) {
int left = 0;
int zeroes = 0;
int max = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) {
zeroes++;
}
while (zeroes > 1) {
if (nums[left] == 0) {
zeroes--;
}
left++;
}
max = Math.max(max, right - left);
}
return max;
}
}Complexity
Each element enters and leaves the sliding window at most once, so the time complexity isO(n), where n is the length of the array. The solution uses only a few variables to maintain the window, so the extra space complexity is
O(1).