[Problem] Longest Subarray of 1's After Deleting One Element

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

Problem 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

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].

Approach

Sliding window problem which can be derived from the idea that there is a maximum number of zeros that can be included in the subarray. Very similar to a previous problem (Max consecutive ones iii).

Same approach as other sliding window problems, we can keep right as a index that continues to iterate throughout the main array, and shift left if there are to many zeros inside the subarray.

Solution

def longestSubarray(self, nums):
    zerocnt = 0
    maxlen = 0
    left = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zerocnt += 1
        while zerocnt > 1:
            if nums[left] == 0:
                zerocnt -= 1
            left += 1
        
        maxlen = max(maxlen, right - left)
    
    return maxlen