1493. Longest Subarray of 1's After Deleting One Element

Medium · solved 2026-10-01 · Open on LeetCode

sliding-windowarray

Time O(n) · Space O(1)

How to get there

From every start to one sliding window

1. Restate what a valid answer looks like. Deleting one element from a subarray leaves all 1’s exactly when the subarray holds at most one zero. So the question becomes: what is the longest subarray with at most one zero? The answer is its length minus 1, because the deletion is required: [1, 1, 1] gives 2.

2. Try it by hand, from every start. On [0, 1, 1, 1, 0, 1, 1, 0, 1], start at index 0 and extend right until a second zero appears: [0, 1, 1, 1] is the longest from there. Then start at index 1 and extend again, and notice the work repeats: indices 1 to 3 were just read, and they still fit.

3. Ask what the repeated scan already knew. Fix a start and grow the end: the zero count only goes up. Once it passes 1, every longer window from that start fails too. So when the window breaks, the start must move forward, and it never has to move back. Nothing the scan learned needs to be thrown away.

4. What to carry: the window and its zero count. Keep the start left, the end right, and how many zeros lie between. Each step of right adds one cell; while the window holds two zeros, left drops cells until it holds one. Each index enters once and leaves at most once, so the whole pass is O(n).

This is Max Consecutive Ones III with k = 1, recorded one shorter.

The reusable recipe: for the longest subarray whose count of something must stay under a limit, and the count only grows as the window grows, slide a window: the right edge adds, the left edge drops until the window is valid again, then record.

Let the variables' meanings write the loop

What each variable always means, after each pass of the loop:

Variable	Always means
`left`, `right`	the window is `nums[left..right]`, and it holds at most one zero
`zeros`	how many zeros lie in `nums[left..right]`
`best`	the longest valid window so far, minus the one deleted element

Each statement is the smallest change that keeps those meanings true:

Code	What happened	What it restores
`if num == 0: zeros += 1`	`right` moved one cell, bringing in `num`	`zeros` counts the new cell
`while zeros > 1:`	the new cell may be a second zero	the window must hold at most one zero again
`if nums[left] == 0: zeros -= 1`, then `left += 1`	the leftmost cell leaves	`zeros` stops counting a cell no longer in the window
`best = max(best, right - left)`	the window is valid again	its length is `right - left + 1`; minus the deletion, `right - left`

The while stops as soon as one zero has left, so the window it leaves behind is the longest valid one ending at right.

The method carries to other sliding windows: state what the window and its counters mean, then each move of either edge is followed by the one update that keeps those meanings true.

Alternatives compared

Approach	Time	Space	How it works
Brute force	O(n²)	O(1)	From each start, extend the end until the window holds a second zero.
Runs of 1’s	O(n)	O(1)	Track the run of 1’s ending here and the run just before the last zero. Deleting that zero joins them, so the answer is the largest sum of the two. An array with no zero needs 1 subtracted.
Sliding window (chosen)	O(n)	O(1)	right adds a cell; left drops cells until the window holds at most one zero.
Non-shrinking window	O(n)	O(1)	left moves at most one step per step of right, so the window never shrinks and its final size minus 1 is the answer.

The sliding window keeps one rule — the window holds at most one zero after every step — and the mandatory deletion is the same - 1 for every window. Runs of 1’s is as fast, but the all-1’s array needs its own case.

solution.py

class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        left = zeros = best = 0

        for right, num in enumerate(nums):
            if num == 0:
                zeros += 1

            while zeros > 1:
                if nums[left] == 0:
                    zeros -= 1
                left += 1

            best = max(best, right - left)

        return best

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.