Longest Subarray of 1s After Deleting One Element

Share

Given a binary array nums, delete one element and return the size of the longest non-empty subarray containing only 1s.

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

Solution Approach

Sliding window allowing at most one zero. The result is window size minus 1 (the deleted element).

  • Use same pattern as max consecutive ones with k=1 (allow one zero).
  • The answer is maxWindowSize - 1 (we must delete exactly one element).
  • Edge case: if no zeros in array, answer is n-1.
Java
class Solution {
    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 the deleted element
        }
        return max;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)