1493.Longest_Subarray_of_1's_After_Deleting_One_Element(Medium).md

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

Date and Time: Oct 7, 2024, 16:49 (EST)

Link: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/

Question:

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.

Walk-through:

Maintain a sliding window with at most one 0. We reset after_zero = 0 when n == 0, and update curSum = after_zero + 1.

There is one difference between the previous problem is that we always return res - 1.

Note: we use after_zero to keep track of the number of counts of 1 after a zero. Because when we encounter the first 0, it is fine to still counting 1s, but when we encounter another 0, we should only count number of 1s after the previous 0. Similar to maintain a window from previous 0 to the current 0 (noninclusive).

Python Solution:

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        # maintain sliding window with counts by curSum, res, after_zero
        # reset after_zero = 0 when n == 0, and update curSum
        # otherwise, increment both curSum, res
        # always return length - 1

        # TC: O(n), SC: O(1)
        after_zero = curSum = res = 0
        for n in nums:
            if n == 1:
                curSum += 1
                after_zero += 1
            else:
                curSum = after_zero + 1
                after_zero = 0
            res = max(res, curSum)
        return res - 1

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