Longest Subarray of 1s After Deleting One Element — Solution

Problem

You are given a binary array (containing only 0s and 1s). You must delete exactly one element — your choice of which index. Return the length of the longest contiguous subarray of all 1s that remains after the deletion.

• Input: nums = [1, 1, 1, 0, 1, 1, 1, 1, 1]
• Output: 8
• Explanation: Deleting the 0 at index 3 leaves eight consecutive 1s.

Note that if the array contains no zeros (e.g., [1, 1, 1]), you still must delete one element, so the best you can achieve is n − 1 = 2.

Intuition

Think of the problem as finding the longest window that contains at most one zero — deleting that zero yields a run of 1s equal to the window size minus one. A sliding window keeps the window valid by advancing the left boundary whenever a second zero enters. Because the deletion is mandatory, the answer is always window_size − 1 (right − left), even when the window holds no zeros at all.

Approach 1 — Brute Force

For each index, skip that element and count the longest run of 1s in the remaining sequence.

1. For every index skip from 0 to n−1, treat it as the deleted position.
2. Scan the full array, accumulating a run of consecutive 1s but treating skip as absent.
3. Reset the run count when a 0 that wasn't deleted is encountered.
4. Track the global maximum across all candidate deletions.

1def longestSubarray(self, nums: list[int]) -> int:
2    max_length = 0
3    for skip in range(len(nums)):
4        current_run = 0
5        for i, value in enumerate(nums):
6            if i == skip:
7                continue  # treat this index as deleted
8            if value == 1:
9                current_run += 1
10                max_length = max(max_length, current_run)
11            else:
12                current_run = 0  # undeleted zero resets the run
13    return max_length

Time: O(n²) — each of the n candidate deletions triggers a full O(n) scan.
Space: O(1) — only counters; no extra data structures.

Approach 2 — Sliding Window

Maintain a window [left, right] that contains at most one zero. The answer for any valid window is right − left — that's the window size minus the one element we always delete.

1. Initialize left = 0 and zero_count = 0.
2. Advance right one step at a time; if nums[right] == 0, increment zero_count.
3. While zero_count > 1, shrink from the left: if nums[left] == 0, decrement zero_count; then advance left.
4. Record right − left as a candidate answer (one element from the window is always deleted).
5. Return the maximum recorded value.

1def longestSubarray(self, nums: list[int]) -> int:
2    left = 0
3    zero_count = 0
4    max_length = 0
5    for right in range(len(nums)):
6        if nums[right] == 0:
7            zero_count += 1
8        # Shrink until the window holds at most one zero
9        while zero_count > 1:
10            if nums[left] == 0:
11                zero_count -= 1
12            left += 1
13        # right - left = window size minus the one mandatory deletion
14        max_length = max(max_length, right - left)
15    return max_length

Time: O(n) — each element enters and exits the window at most once.
Space: O(1) — only two pointers and a zero counter.

Complexity Summary

Common Mistakes

• Using right − left + 1 instead of right − left — the window size includes the one element being deleted; forgetting to subtract 1 overcounts by one for every window.
• Skipping the deletion on all-ones arrays — the problem requires deleting exactly one element regardless; returning n for [1, 1, 1] is wrong. right − left naturally yields n − 1 here.
• Advancing left with if instead of while — when consecutive zeros appear (e.g., [1, 0, 0, 1]), a single if leaves two zeros in the window after moving left once.
• Not updating zero_count when shrinking — incrementing left without checking nums[left] corrupts the zero count, allowing invalid windows with more than one zero.
• Treating nums[right] == 1 as the only update — the zero count must be incremented on nums[right] == 0, not conditionally updated at the end of the loop; misplacing that check causes the window constraint to lag by one step.

Related Problems

• Max Consecutive Ones III — direct generalization allowing up to k zeros in the window instead of exactly one
• Longest Repeating Character Replacement — same sliding window skeleton but the constraint is on a character replacement budget
• Minimum Window Substring — harder sliding window that tracks full character frequency maps inside the window
• Longest Substring Without Repeating Characters — sliding window that shrinks on a uniqueness violation; same structural pattern
• Contiguous Array — finds the longest subarray with equal 0s and 1s; shares the intuition of tracking zero counts to identify valid subarrays