1493. Longest Subarray of 1's After Deleting One Element

Description

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example 1:

  Input: nums = [1,1,0,1]
  Output: 3
  Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

  Input: nums = [0,1,1,1,0,1,1,0,1]
  Output: 5
  Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

My Solution

 
// using sliding window
/**
 * @param {number[]} nums
 * @return {number}
 */
 var longestSubarray = function(nums) {
  let left = 0;
  let zeroCount = 0
  let maxLen = 0;
 
  for(let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) {
      zeroCount++;
    } 
 
    while (zeroCount > 1) {
      // If the number of zeros exceeds one, move the left pointer to the right,
      // reducing the number of zeros.
      if (nums[left] === 0) {
        zeroCount--;
      }
      left++;
    }
 
    // The current window's length is right - left + 1.
    // However, according to the problem's condition that one element must be deleted,
    // the actual length becomes right - left.
    maxLen = Math.max(maxLen, right - left);
  }
  return maxLen;
};
 

Explanation

1. Initialize Variables: Start with two pointers, left and right, at the start of the array. left marks the beginning of the window, and right marks the end. Also, have a zeroCount to keep track of the zeros in the window, and a maxLength to store the longest sequence found.
2. Expand Window: Move right pointer to the right (increase it) to make the window bigger. Every time you see a 0, increase zeroCount.
3. Check Zeros: If zeroCount is more than 1, it means there are too many zeros in our current window. We need only one or none.
4. Shrink Window: Start moving left pointer to the right (increase it) to make the window smaller from the left side. Do this until zeroCount is 1 or less again. If you pass a 0 while moving left, decrease zeroCount.
5. Calculate Length: The current window length is the difference between right and left. Update maxLength if this length is the longest found so far.
6. Repeat: Keep expanding the window by moving right until you've checked the whole array.
7. Return Result: The longest sequence length is maxLength. Remember, we subtract one from the window length because we're allowed to remove one 0