How do you solve Longest Subarray of 1's After Deleting One Element?

Use two pointers (left and right) to maintain a sliding window that contains at most one zero. Increment zero_count when a zero is encountered at right. If zero_count exceeds one, move left forward, decrementing zero_count when a zero is passed. Track the maximum window size during iteration. Since one element must be deleted, subtract one from the final maximum window size before returning.

Longest Subarray of 1's After Deleting One Element

Q: What is the time complexity of Longest Subarray of 1's After Deleting One Element?

O(n). Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time complexity.

Q: What pattern does Longest Subarray of 1's After Deleting One Element use?

The Pattern: Sliding Window (Variable Size with Constraint) The Heuristic: When asked for the longest subarray satisfying a constraint on the number of certain elements (e.g., at most one zero), use a sliding window that expands until the constraint is violated, then contracts from the left to restore validity, tracking the maximum window size throughout.

Medium Sliding Window

Problem

Given a binary array nums, return the length of the longest subarray containing only 1s after deleting exactly one element from nums.

1 ≤ nums.length ≤ 10⁵
nums[i] is either 0 or 1

Example

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

Output: 5

The longest subarray of 1s after deleting one element is obtained by deleting the zero at index 2, resulting in the subarray [1,1,1,1,1] of length 5. The algorithm uses a sliding window to track the number of zeros in the current window. It expands the right pointer, counting zeros, and when more than one zero is included, it moves the left pointer forward to exclude zeros until only one zero remains. The maximum window size found during this process is 6, but since one element must be deleted, the final answer is 6 - 1 = 5.

Approach

Straightforward Solution

A brute-force approach would check every subarray, count zeros, and track the longest with at most one zero, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

The problem reduces to finding the longest contiguous subarray containing at most one zero, because deleting one element corresponds to removing one zero from the subarray to get all ones.

Path to Optimal

Preview

Recognizing the problem as a longest subarray with at most one zero allows the use of a sliding window. The window expands by moving the right pointer and counting zeros…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers (left and right) to maintain a sliding window that contains at most one zero. Increment zero_count when a zero is encountered at right…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time complexity.

Space

O(1)

Only a fixed number of variables are used to track pointers and zero counts, independent of input size.

Pattern Spotlight

Sliding Window (Variable Size with Constraint)

When asked for the longest subarray satisfying a constraint on the number of certain elements (e.g., at most one zero), use a sliding window that expands until the constraint is violated, then contracts from the left to restore validity, tracking the maximum window size throughout.

Solution

Python

1class Solution:
  def longestSubarray(self, nums: List[int]) -> int:
      left = 0
      zero_count = 0
      longest = 0
6
      for right in range(len(nums)):
          if nums[right] == 0:
              zero_count += 1
10
          while zero_count > 1:
              if nums[left] == 0:
                  zero_count -= 1
              left += 1
15
          longest = max(longest, right - left + 1)
17
      return longest - 1

Step-by-Step Solution

Initialize Sliding Window Pointers and Counters

3left = 0
4zero_count = 0
5longest = 0

Objective

To set up the initial state for the sliding window traversal, including left pointer, zero count, and longest subarray length.

Key Insight

Starting with left at 0 and zero_count at 0 allows the window to expand from the beginning. The longest variable tracks the maximum window size found so far. This setup is essential for the sliding window to correctly maintain the count of zeros and window boundaries.

Interview Quick-Check

Core Logic

Initialize left pointer and zero_count to track the number of zeros in the current window.

State & Boundaries

The window starts empty with left = 0 and zero_count = 0, ready to expand.

Expand Window and Adjust Left Pointer to Maintain At Most One Zero

To iterate over the array with the right pointer, update zero count, and shrink the window from the left when more than one zero is included.

Track Maximum Window Size and Return Adjusted Result

To update the longest subarray length during iteration and return the final answer accounting for the required deletion.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 18 Critical

return longest - 1

Return the longest subarray length minus one to account for the deleted element.

Subtracting one adjusts for the mandatory deletion, yielding the correct length of the longest subarray of 1s after removing one element.

Line 11 Critical

while zero_count > 1:

While the window contains more than one zero, shrink it from the left.

This loop ensures the window remains valid by removing elements from the left until only one zero remains, maintaining the problem's constraint.

Line 13 Critical

zero_count -= 1

Decrement zero_count when a zero is removed from the window.

This adjustment keeps zero_count accurate as the window contracts, preventing invalid window states.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does the algorithm subtract one from the maximum window size before returning the result?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Longest Subarray of 1's After Deleting One Element from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Longest Subarray of 1's After Deleting One Element drill

or drill a free problem

1	`class Solution:`
2	`def longestSubarray(self, nums: List[int]) -> int:`
3	`left = 0`
4	`zero_count = 0`
5	`longest = 0`
6
7	`for right in range(len(nums)):`
8	`if nums[right] == 0:`
9	`zero_count += 1`
10
11	`while zero_count > 1:`
12	`if nums[left] == 0:`
13	`zero_count -= 1`
14	`left += 1`
15
16	`longest = max(longest, right - left + 1)`
17
18	`return longest - 1`