#1493 - Longest Subarray of 1's After Deleting One Element

MediumSliding Window

Given a binary array nums, return the size of the longest non-empty subarray containing only 1's in the resulting array after deleting exactly one element. Return 0 if there is no such subarray.

Input	Output
nums = [1,1,0,1,1,1,0,1]	5
nums = [0,1,1,1,0,1,1,0,1]	5
nums = [1,1,1]	2

Solution Space

Try it

/**
 * Returns the longest subarray of 1's after deleting exactly one element.
 *
 * Equivalent to "Max Consecutive Ones III" with k = 1, but because one
 * element must be deleted the answer is always windowSize − 1.
 *
 * @param nums Binary array
 * @returns    Length of longest all-1 subarray after one deletion
 */
export function longestSubarray(nums: number[]): number {
  let left = 0;
  let zeros = 0;
  let max = 0;

  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;

    while (zeros > 1) {
      if (nums[left] === 0) zeros--;
      left++;
    }

    // −1 because we must delete exactly one element
    max = Math.max(max, right - left);
  }

  return max;
}

Approach: sliding window with at most one zero – identical to problem 21 with `k = 1`, but the result is `windowSize − 1` because exactly one element must be removed.

Time: O(n) – each index is visited at most twice.

Space: O(1) – constant extra variables.

#1456 Maximum Number of Vowels in a Substring of Given Length

#724 Find Pivot Index