TL;DR
Slide a window that holds at most one zero: O(n) time, O(1) space. A prefix/suffix DP is an equally valid O(n) time, O(n) space framing.
Approach 1 — Brute force
Try deleting each index, then scan the resulting array for its longest run of ones.
def longestSubarray(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 only useful deletion is at an index that bridges two runs of ones (a 0 between them, or a forced 1 when there are no zeros). 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, and symmetrically right[i] = right[i+1] + 1 if nums[i]==1 else 0. Deleting index i then yields left[i-1] + right[i+1] ones.
def longestSubarray(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) gives left[1] + right[3] = 2 + 1 = 3, which is the best.
Complexity: O(n) time, O(n) space.
Approach 3 — Sliding window (space-optimized, the intended solution)
Deleting one element is equivalent to keeping a window that contains 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 equal the window length minus the one deleted slot.
def longestSubarray(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 window occurs at right = 6 with left = 1. The window [1..6] = 1,1,1,0,1,1 holds exactly one zero (index 4) and has 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, so the answer is 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 standard sliding-window template; here k = 1 and the bad element is the zero you delete. When a problem lets you remove or replace up to k items, translate it into a constraint on the window’s contents. Note that “delete exactly one” still costs one slot even when nothing needs fixing.