Longest Subarray of 1's After Deleting One Element

Solving tips

Reframe 'delete one element' as a sliding window containing at most one zero - that single zero is the deleted slot.
Grow the right edge; when zeros exceed 1, advance left past the first zero. The kept ones = window size minus one.
Return right - left (window length minus the mandatory deletion), so an all-ones array of length k correctly yields k-1.
Target O(n) time, O(1) space; a prefix/suffix ones-count DP is an equally valid O(n) framing.

Problem

Given a binary array nums, you must delete exactly one element. After the deletion, return the length of the longest contiguous run of 1s in the resulting array. If every possible result is empty (i.e. the array was all zeros, or a single element), return 0.

Note the “exactly one deletion” rule: even an all-1s array must give one element up.

Examples

nums = [1,1,0,1] → 3 — delete the 0 at index 2 to get [1,1,1].
nums = [0,1,1,1,0,1,1,0,1] → 5 — delete the 0 at index 4, joining the two runs into 1,1,1,1,1.
nums = [1,1,1] → 2 — no zeros, but you must still delete one 1, leaving [1,1].

Constraints

1 <= nums.length <= 10⁵
nums[i] is 0 or 1.

Think about it first

Hint 1

Deleting one element and joining its neighbors is the same as choosing a window that contains at most one zero — that single zero is the element you delete. The kept count is then the number of ones in that window.

Hint 2

DP view: for each index compute left[i] = consecutive ones ending just before i, and right[i] = consecutive ones starting just after i. Treating position i as the deleted slot, you can bridge left[i] + right[i] ones.

Hint 3

Or slide a window [l, r] rightward, counting zeros inside; when the count exceeds 1, advance l. The answer is the largest (window size − 1), since exactly one element is always removed.

TL;DR

Sliding window allowing at most one zero — O(n) time, O(1) space. A prefix/suffix DP is the equally valid O(n)/O(n) framing.

Approach 1 — Brute force

Try deleting each index, then scan the resulting array for its longest run of ones.

class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        n = len(nums)
        best = 0
        for d in range(n):                      # delete index d
            run = longest = 0
            for i in range(n):
                if i == d:
                    run = 0
                    continue
                run = run + 1 if nums[i] == 1 else 0
                longest = max(longest, run)
            best = max(best, longest)
        return best

Complexity: O(n) deletions × O(n) scan = O(n²) time. At n = 10⁵ that’s 10¹⁰ operations — far too slow.

Approach 2 — Prefix/suffix DP

The insight: the only useful deletion is at a 0 (or a forced 1 if there are no zeros) that bridges two runs of ones. Precompute how many ones run up to and away from each index.

Recurrence: left[i] = left[i-1] + 1 if nums[i]==1 else 0; symmetrically right[i] = right[i+1] + 1 if nums[i]==1 else 0. Deleting index i yields left[i-1] + right[i+1] ones.

class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        n = len(nums)
        left = [0] * n     # ones ending at i (inclusive)
        right = [0] * n    # ones starting at i (inclusive)
        for i in range(n):
            left[i] = left[i - 1] + 1 if i > 0 and nums[i] == 1 else (1 if nums[i] == 1 else 0)
        for i in range(n - 1, -1, -1):
            right[i] = right[i + 1] + 1 if i < n - 1 and nums[i] == 1 else (1 if nums[i] == 1 else 0)

        best = 0
        for i in range(n):
            l = left[i - 1] if i > 0 else 0
            r = right[i + 1] if i < n - 1 else 0
            best = max(best, l + r)     # delete index i, bridge the two sides
        return best

Walkthrough (nums = [1,1,0,1]): left = [1,2,0,1], right = [2,1,0,1]. Deleting index 2 (the zero): left[1] + right[3] = 2 + 1 = 3. Best 3. ✓

Complexity: O(n) time, O(n) space.

Approach 3 — Sliding window (space-optimized, the intended solution)

The insight: “delete one element” ≡ “keep a window containing at most one zero.” Grow the window’s right edge; whenever it holds two zeros, shrink from the left past the first zero. The kept ones = window length minus one deleted slot.

class Solution:
    def longestSubarray(self, nums: list[int]) -> int:
        left = zeros = best = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zeros += 1
            while zeros > 1:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            # window [left, right] has <= 1 zero; we always delete one element
            best = max(best, right - left)
        return best

Walkthrough (nums = [0,1,1,1,0,1,1,0,1]): the best moment is right = 6 with left = 1 — window [1..6] = 1,1,1,0,1,1 holds exactly one zero (index 4), size 6, contributing right - left = 6 - 1 = 5. When right = 7 brings a second zero, left advances to 5 and the window shrinks. No later window beats 5. Answer 5. ✓

Complexity: O(n) time (each index enters and leaves the window once), O(1) space.

Common pitfalls

Forgetting deletion is mandatory: an all-ones array of length k must return k - 1, not k. Using right - left (window size minus one) handles this automatically.
Returning right - left + 1 (the raw window size) — that counts the deleted element as if it stayed.
nums.length == 1: [1] → 0 and [0] → 0; the window formula gives 0 for both.
Off-by-one in the prefix/suffix version when i is at either boundary — guard i-1 and i+1.

Pattern takeaway

“Longest window with at most k bad elements” is a canonical sliding-window template; here k = 1 and the “bad” element is the zero you delete. When a problem lets you remove/replace up to k items, translate it into a constraint on the window’s contents — and remember that “delete exactly one” costs you one slot even when nothing needs fixing.