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

The problem

You get a binary array nums. You must delete exactly one element. Return the length of the longest non-empty subarray of only 1s in the array that’s left, or 0 if there isn’t one.

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

Delete the 0 at index 4: indices 1 to 6 become 1, 1, 1, 1, 1, a run of 5.

How to think about it

Start with brute force. Try deleting each element in turn, then scan for the longest run of 1s. That’s n deletions times an O(n) scan, so O(n²).

Reframe the deletion. After the deletion, the run of 1s you end up with came from a stretch of the original array that contained at most one zero (the one you deleted). If the stretch had no zero, you still have to delete something, and deleting one of its own 1s shortens it by one. Either way, the run you keep is the stretch’s length minus one.

The key insight: it’s “longest window with at most one zero”, minus one. That’s Max Consecutive Ones III with k = 1. Grow the window, count zeros, and shrink from the left whenever there are two. For each valid window nums[start..i], the answer candidate is (i - start + 1) - 1 = i - start.

Which pattern is this? A variable-size sliding window with a zero counter. The tell is “longest run of 1s with one change allowed”.

Approach

1. Keep start = 0, zeros = 0, best = 0.
2. For each i, increase zeros if nums[i] is 0.
3. While zeros > 1, move start right, decreasing zeros when a 0 leaves.
4. Update best = max(best, i - start), which is the window length minus the deleted slot.
5. Return best.

Solution

def longest_subarray_after_del(nums):
    start = 0; zeros = 0; best = 0
    for i, x in enumerate(nums):
        if x == 0: zeros += 1
        while zeros > 1:                       # at most one zero allowed
            if nums[start] == 0: zeros -= 1
            start += 1
        best = max(best, i - start)  # minus the one deletion
    return best
# longest_subarray_after_del([1,1,0,1]) -> 3

Dry run

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

(At i = 4 the second zero pushes start past index 0.) The answer is 5.

Complexity

• Time: O(n). Both pointers only move right.
• Space: O(1). Three integers.

Edge cases and pitfalls

• All 1s ([1, 1, 1]): you still must delete one, so the answer is 2, not 3. The i - start formula handles this.
• All 0s returns 0.
• A single element returns 0: after deleting it, nothing is left.
• Returning i - start + 1 forgets the mandatory deletion and over-counts by one.
• Splitting into runs of 1s and joining neighbours across single zeros also works, but the window version has fewer special cases.

Related problems

• Max Consecutive Ones III (LeetCode 1004): the general “at most k zeros” window.
• Longest Repeating Character Replacement (LeetCode 424): the same budget idea over 26 letters.
• Fruit Into Baskets (LeetCode 904): another longest window with a limit on what’s inside.