Longest Subarray of 1's After Deleting One Element

Sliding Window

20 min

Problem Statement

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

Example 1:

Input: nums = [1,1,0,1]

nums: [1, 1, 0, 1]

Output: 3

After deleting the 0, the subarray [1,1,1] has length 3.

Solution

We can use a sliding window to solve this problem. The window will contain at most one zero. We expand the window by moving the right pointer. If the window contains more than one zero, we shrink it from the left until it has at most one zero again.

Algorithm Steps

Initialize `maxLength` to 0, `zeroCount` to 0, and a left pointer `l` to 0.
Iterate through the array with a right pointer `r`. If `nums[r]` is 0, increment `zeroCount`.
While `zeroCount` is greater than 1, if `nums[l]` is 0, decrement `zeroCount`. Then, increment `l`.
Update `maxLength` with the maximum of `maxLength` and the current window size (`r - l`).

Longest Subarray of 1's After Deleting One Element

Sliding Window Approach

Progress1 / 1

Ready to start the visualization

nums

Zero Count

Max Length

Longest Subarray of 1's After Deleting One Element Solution


class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        zero_count = 0
        l = 0
        max_len = 0

        for r in range(len(nums)):
            if nums[r] == 0:
                zero_count += 1
            
            while zero_count > 1:
                if nums[l] == 0:
                    zero_count -= 1
                l += 1
            
            max_len = max(max_len, r - l)
            
        return max_len