LeetCode 1493 - Longest Subarray of 1's After Deleting One Element

This problem asks us to find the longest contiguous subarray of 1s in a binary array nums after deleting exactly one ele

leetcodemediumarraydynamic-programmingsliding-window

LeetCode Problem 1493

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Sliding Window

Solution

Problem Understanding

This problem asks us to find the longest contiguous subarray of 1s in a binary array nums after deleting exactly one element. In other words, we can remove a single element (which could be 0 or 1) and then consider the longest block of consecutive 1s that remains. The array is binary, so elements are either 0 or 1. The function must return the length of this longest subarray.

The constraints indicate that the array can be large, up to 100,000 elements, so any solution that examines every possible subarray naively will be too slow. The array is guaranteed to have at least one element, but it may consist entirely of 1s or entirely of 0s. Since we must delete one element, even if the array is all 1s, the maximum subarray length is len(nums) - 1. Similarly, if the array is all 0s, the output must be 0.

Important edge cases include arrays that are all 1s, arrays that are all 0s, and arrays where 0s are at the start or end, which could affect how the "delete one element" operation impacts the longest sequence of 1s.

Approaches

A brute-force approach would consider deleting each element in the array and computing the length of the longest consecutive 1s for the resulting array. This involves iterating through the array for every deletion and then scanning for consecutive 1s, leading to a quadratic time complexity. This is correct but inefficient for arrays of length up to 100,000.

The key observation that enables a more efficient solution is that we only need to keep track of segments of 1s separated by at most one 0. By considering a sliding window where we allow at most one 0 to be skipped (as if it is deleted), we can find the maximum combined length of two consecutive 1 segments separated by a single 0. This turns the problem into a sliding window problem where the window can contain at most one 0.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Delete each element and compute the longest subarray of 1s
Optimal O(n) O(1) Sliding window approach keeping track of at most one zero

Algorithm Walkthrough

  1. Initialize two pointers left and right at the start of the array. These will define the sliding window of elements being considered.
  2. Initialize a variable zero_count to keep track of the number of zeros in the current window.
  3. Initialize a variable max_len to store the maximum length of a valid window found so far.
  4. Expand the right pointer through the array. Each time a zero is encountered, increment zero_count.
  5. If zero_count exceeds 1, shrink the window from the left until there is at most one zero in the window, decrementing zero_count whenever a zero leaves the window.
  6. Update max_len as the size of the current window minus one, because we must delete exactly one element.
  7. Continue until right reaches the end of the array. Return max_len.

Why it works: By keeping a sliding window with at most one zero, we effectively consider deleting that zero to maximize consecutive 1s. The invariant is that zero_count <= 1 ensures we can always remove one zero to form a valid subarray.

Python Solution

from typing import List

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        left = 0
        zero_count = 0
        max_len = 0
        
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1
            
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            
            max_len = max(max_len, right - left)
        
        return max_len

The Python code iterates over the array with a right pointer while maintaining a count of zeros. If more than one zero is in the window, it moves the left pointer forward to reduce the zero count to at most one. The length of the current valid window minus one is used to update the maximum length.

Go Solution

func longestSubarray(nums []int) int {
    left, zeroCount, maxLen := 0, 0, 0
    
    for right := 0; right < len(nums); right++ {
        if nums[right] == 0 {
            zeroCount++
        }
        
        for zeroCount > 1 {
            if nums[left] == 0 {
                zeroCount--
            }
            left++
        }
        
        if right - left > maxLen {
            maxLen = right - left
        }
    }
    
    return maxLen
}

In Go, the logic mirrors Python. The for loop uses integer indices, and variables are initialized using :=. The slice nums is used directly, and window length is computed using right - left.

Worked Examples

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

right nums[right] zero_count left max_len
0 0 1 0 0
1 1 1 0 1
2 1 1 0 2
3 1 1 0 3
4 0 2 0->1 3
5 1 1 2 4
6 1 1 2 5
7 0 2 3->5 5
8 1 1 6 5

Result: 5

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass over the array using sliding window
Space O(1) Only constant extra variables used

The optimal solution scans the array once while maintaining a running count of zeros and updating the maximum length, so both the time and space complexity are minimal.

Test Cases

# Provided examples
assert Solution().longestSubarray([1,1,0,1]) == 3  # Deleting 0 gives [1,1,1]
assert Solution().longestSubarray([0,1,1,1,0,1,1,0,1]) == 5  # Deleting middle 0
assert Solution().longestSubarray([1,1,1]) == 2  # Must delete one element

# Edge cases
assert Solution().longestSubarray([0,0,0]) == 0  # Only zeros
assert Solution().longestSubarray([1,0,1,0,1]) == 3  # Deleting any zero in middle
assert Solution().longestSubarray([1]) == 0  # Single element, must delete it
assert Solution().longestSubarray([1,0,1,1,1,0,1,1]) == 5  # Mixed zeros
assert Solution().longestSubarray([1]*100000) == 99999  # Large array, all ones
Test Why
[1,1,0,1] Basic case with one zero
[0,1,1,1,0,1,1,0,1] Longer array with multiple zeros
[1,1,1] All ones, must delete one
[0,0,0] All zeros
[1,0,1,0,1] Multiple small segments separated by zeros
[1] Single-element array
[1]*100000 Stress test for large input

Edge Cases

One important edge case is an array containing all 1s. Since we must delete one element, the longest subarray is len(nums) - 1. Another edge case is an array of all 0s, which should return 0 because removing one 0 still leaves no 1s. A third edge case is a single-element array, which after deletion becomes empty, so the function should return 0. The sliding window implementation correctly handles these cases because it tracks zeros and ensures the maximum length accounts for deleting exactly one element.