We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Subarray of 1's After Deleting One Element

Number: 1586

Difficulty: Medium

Paid? No

Companies: Yandex, Meta, Google, Amazon, Apple, Adobe, Tinkoff

Problem Description

Given a binary array nums, delete exactly one element from it. Return the size of the longest non-empty subarray containing only 1's from the resulting array. If there is no such subarray, return 0.

Key Insights

  • Utilize a sliding window approach to efficiently traverse the array.
  • Keep track of the count of zeros inside the window and ensure that it never exceeds one (simulating deletion).
  • When the window contains more than one zero, move the left pointer until the condition is restored.
  • Remember the deletion is mandatory, so when all elements are 1's, the answer is (total 1's minus 1).

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in nums. Space Complexity: O(1), as only a few variables are used.

Solution

The approach involves using a sliding window with two pointers, left and right. As we iterate through nums with the right pointer, we count zeros. If more than one zero is found, move the left pointer until there is at most one zero in the window. The current valid window length is given by (right - left) because one element must be removed. This method efficiently finds the maximum subarray length after deletion.

Code Solutions

# Python solution with clear comments
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        # Initialize pointers and counter for zeros in the current window
        left = 0
        zero_count = 0
        max_length = 0
        
        # Iterate over nums using the right pointer
        for right in range(len(nums)):
            # If the current number is 0, increment zero_count
            if nums[right] == 0:
                zero_count += 1
            
            # If there are more than one zero, shrink the window from the left
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            
            # Update max_length with the current window size minus one deletion
            max_length = max(max_length, right - left)
        
        return max_length
← Back to All Questions