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

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.

Approach

Input: A binary array nums, requiring the deletion of exactly one element.

Output: Return the length of the longest non-empty subarray containing only 1s after the deletion.

This problem falls under the Variable-length Sliding Window category.

We can use two pointers to maintain a sliding window, keeping a variable to track the number of 0s currently in the window. When the count of 0s in the window does not exceed 1, it means the current window is valid, so we try to update the maximum length of consecutive 1s (since we must delete one element, we can keep at most one 0 within our valid window). When the number of 0s exceeds 1, we must move the left pointer to shrink the window until the count of 0s returns to the permitted range.

Throughout the process, we move the right pointer to expand the window while dynamically adjusting the left boundary, always recording the maximum subarray length that satisfies the condition. Finally, return this maximum value.

Implementation

python

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left = 0  # Left boundary of the sliding window
        zero_count = 0  # Number of 0's inside the current window
        max_len = 0  # Max length of consecutive 1s (allowing for one 0 to be deleted)

        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1

            # When number of 0s in window exceeds 1, move left boundary rights
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1

            # At this point, the window has at most one 0. Length is right - left
            max_len = max(max_len, right - left)

        return max_len

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function(nums) {
    let zeroNum = 0;

    let l = 0;
    let ans = 0;
    for (let r = 0; r < nums.length; r++) {
        if (nums[r] == 0) zeroNum++;

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

        ans = Math.max(ans, r - l);
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

1493. Longest Subarray of 1's After Deleting One Element (English)1493. 删掉一个元素以后全为 1 的最长子数组 (Chinese)