Longest Subarray of 1s After Deleting One Element

Share

After deleting one element, find the longest subarray of all 1s.

Example 1
Input: nums=[1,1,0,1] → Output: 3
Example 2
Input: nums=[0,1,1,1,0,1,1,0,1] → Output: 5

Solution Approach

Sliding window: allow at most one 0 in the window.

  • Sliding window with zero count
  • Expand right; if nums[right]==0 increment zeros
  • While zeros > 1: if nums[left]==0 decrement zeros; left++
  • Window size - 1 is valid length (we must delete exactly one)
  • Track max
Java
public int longestSubarray(int[] nums) {
    int left = 0, zeros = 0, max = 0;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) zeros++;
        while (zeros > 1) {
            if (nums[left] == 0) zeros--;
            left++;
        }
        max = Math.max(max, right - left); // -1 for deleted element
    }
    return max;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)