#1493

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Subarray of 1's After Deleting One Element

Solve LeetCode 1493 by tracking runs of 1s around one deletion using a tight sliding window or state transition DP.

array dynamic programming sliding window

Problem Statement

You are given a binary array and must remove exactly one element from it. After that deletion, measure the longest remaining contiguous subarray made only of 1s, and return its length. Because the deletion is mandatory, an input like [1,1,1] does not return 3; it returns 2 after removing one position.

A useful way to think about this problem is that deleting one zero can connect two neighboring runs of 1s, while deleting a 1 may be necessary when the array has no zero at all. For example, nums = [1,1,0,1] becomes length 3 by deleting the zero, but arrays with multiple zeros force you to choose the best place to bridge only one gap.

Examples

Example 1

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

Output: 3

After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2

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

Output: 5

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

Example 3

Input: nums = [1,1,1]

Output: 2

You must delete one element.

Constraints

1 <= nums.length <= 105
nums[i] is either 0 or 1.

Solution Approach

Model the deletion as one allowed break

The exact trade-off in this problem is that one removed element can erase at most one zero gap between runs of 1s. That means the answer is the longest region containing at most one zero, because deleting that zero leaves only 1s behind. This framing immediately converts the problem from brute-force deletion checks into a linear scan.

Use state transition DP or an equivalent sliding window

A compact DP keeps two values while scanning nums: the current streak of 1s without any deletion, and the best streak ending here after already deleting one element. When you see a 1, both streaks extend; when you see a 0, the no-deletion streak resets and the one-deletion streak becomes the previous no-deletion streak, as if this zero were removed. The sliding window version expresses the same idea by maintaining a window with at most one zero and taking window size minus one.

Handle the mandatory deletion rule carefully

The most common wrong answer appears on all-ones arrays. Even if there is no zero to remove, you still must delete one element, so the final result is n - 1 rather than n. In the window formulation, subtracting one from the valid window size naturally enforces that rule, and in DP you can track the best valid length under one required deletion.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Both the sliding window and state transition DP scan the array once, so the time complexity is O(N). They store only a few counters or state values, so the space complexity is O(1). This matters for nums.length up to 10^5, where trying every deletion point would be too slow.

What Interviewers Usually Probe

They mention keeping a window with at most one zero, which points directly to the one-deletion sliding window.
They ask what happens on an all-ones array, testing whether you remember the deletion is mandatory.
They ask for an O(N) solution without extra arrays, which favors constant-space state transitions.

Common Pitfalls or Variants

Common pitfalls

Returning the longest run of 1s without subtracting one when the current window contains no zero.
Treating the task as optional deletion and incorrectly answering 3 for nums = [1,1,1].
Resetting too aggressively on zeros and missing that one deleted zero can merge the left and right 1-runs.

Follow-up variants

Allow deleting up to k elements, which generalizes the window from at most one zero to at most k zeros.
Return the actual subarray boundaries after deletion instead of only the maximum length.
Solve the streaming version where bits arrive one by one and you maintain the current best under one deletion.

FAQ

What is the main idea behind Longest Subarray of 1's After Deleting One Element?

Treat the deletion as permission to keep a contiguous region with at most one zero. If a window has one zero, deleting it leaves only 1s; if it has no zero, you still remove one element, so the contribution is window length minus one.

Why does the sliding window work for LeetCode 1493?

This problem only cares whether a segment can become all 1s after one deletion. That is exactly the same as asking whether the segment contains at most one zero, so a two-pointer window can expand greedily and shrink only when zeros exceed one.

How does the state transition dynamic programming pattern apply here?

Use one state for consecutive 1s with no deletion used yet and another for consecutive 1s after one deletion. On a 1, both states extend; on a 0, the deleted-state takes the old no-deletion streak and the no-deletion streak resets to zero.

What should I return for an array of all 1s?

Return n - 1 because one element must be deleted even though there is no zero to remove. This is the most important edge case and the easiest way to lose correctness on this problem.

Is DP better than sliding window for this problem?

They are effectively two views of the same linear-time solution. Sliding window is often easier to explain in interviews, while the DP form makes the state transition around a zero especially explicit.

terminal

Solution

Solution 1: Enumeration

We can enumerate each position $i$ to be deleted, then calculate the number of consecutive 1s on the left and right, and finally take the maximum value.

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left = [0] * (n + 1)
        right = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            if x:
                left[i] = left[i - 1] + 1
        for i in range(n - 1, -1, -1):
            if nums[i]:
                right[i] = right[i + 1] + 1
        return max(left[i] + right[i + 1] for i in range(n))

Solution 2: Two Pointers

The problem is actually asking us to find the longest subarray that contains at most one $0$. The remaining length after deleting one element from this subarray is the answer.

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left = [0] * (n + 1)
        right = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            if x:
                left[i] = left[i - 1] + 1
        for i in range(n - 1, -1, -1):
            if nums[i]:
                right[i] = right[i + 1] + 1
        return max(left[i] + right[i + 1] for i in range(n))

Solution 3: Two Pointers (Optimization)

In Solution 2, we move the left pointer in a loop until $cnt \leq 1$. Since the problem asks for the longest subarray, it means we don't need to reduce the length of the subarray. Therefore, if $\textit{cnt} \gt 1$, we only move the left pointer once, and the right pointer continues to move to the right. This ensures that the length of the subarray does not decrease.

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left = [0] * (n + 1)
        right = [0] * (n + 1)
        for i, x in enumerate(nums, 1):
            if x:
                left[i] = left[i - 1] + 1
        for i in range(n - 1, -1, -1):
            if nums[i]:
                right[i] = right[i + 1] + 1
        return max(left[i] + right[i + 1] for i in range(n))

Continue Practicing

#1477 find two non overlapping sub arrays each with target sum #1425 constrained subsequence sum #1031 maximum sum of two non overlapping subarrays