Longest Subarray of 1's After Deleting One Element
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
nums = [1,1,0,1,1,1]5The 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
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. When the zero count exceeds one, the left pointer moves forward to shrink the window until only one zero remains. This approach maintains a valid window and finds the maximum length in O(n) time.
Optimal Approach
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.
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
| 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 |
Step-by-Step Solution
Initialize Sliding Window Pointers and Counters
| 3 | left = 0
|
| 4 | zero_count = 0
|
| 5 | longest = 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
| 7 | for right in range(len(nums)):
|
| 8 | if nums[right] == 0:
|
| 9 | zero_count += 1
|
| 11 | while zero_count > 1:
|
| 12 | if nums[left] == 0:
|
| 13 | zero_count -= 1
|
| 14 | left += 1
|
Objective
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.
Key Insight
The sliding window expands by moving the right pointer and counting zeros. When the zero count exceeds one, the window is invalid, so the left pointer moves forward to exclude zeros until the window contains at most one zero again. This dynamic adjustment ensures the window always satisfies the problem's constraint, enabling efficient tracking of the longest valid subarray.
Interview Quick-Check
Core Logic
Expand the window by moving right pointer and increment zero_count on zeros; contract from left when zero_count exceeds one to restore validity.
State & Boundaries
The while loop condition zero_count > 1 ensures the window never contains more than one zero.
Common Pitfalls & Bugs
Forgetting to decrement zero_count when moving left past a zero leads to incorrect zero counts and invalid windows.
Track Maximum Window Size and Return Adjusted Result
| 16 | longest = max(longest, right - left + 1)
|
| 18 | return longest - 1 |
Objective
To update the longest subarray length during iteration and return the final answer accounting for the required deletion.
Key Insight
At each step, the current window size (right - left + 1) represents a candidate subarray with at most one zero. Tracking the maximum ensures the longest such subarray is found. Since the problem requires deleting one element, subtracting one from the maximum window size yields the length of the longest subarray of 1s after deletion.
Interview Quick-Check
Core Logic
Update longest with the size of the current valid window and subtract one before returning to account for the deleted element.
Common Pitfalls & Bugs
Returning longest without subtracting one would incorrectly count the deleted element as part of the subarray.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
return longest - 1Return 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.
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.
zero_count -= 1Decrement zero_count when a zero is removed from the window.
This adjustment keeps zero_count accurate as the window contracts, preventing invalid window states.
zero_count = 0Initialize zero_count to track the number of zeros in the current window.
Tracking zeros is essential to enforce the constraint of at most one zero in the window, which corresponds to the one element allowed to be deleted.
zero_count += 1Increment zero_count when a zero is encountered.
Updating zero_count maintains an accurate count of zeros in the current window, which governs window validity.
longest = max(longest, right - left + 1)Update longest with the maximum window size found so far.
Tracking the maximum window size ensures the algorithm returns the longest valid subarray length after iteration.
if nums[right] == 0:Check if the current element at right is zero.
Identifying zeros is critical because the window can contain at most one zero to satisfy the problem's deletion constraint.
if nums[left] == 0:Check if the element at left is zero before moving left pointer.
Detecting zeros at the left boundary is necessary to decrement zero_count correctly when the window shrinks.
left += 1Move the left pointer forward to shrink the window.
Advancing left reduces the window size, restoring validity when zero_count exceeds one.
for right in range(len(nums)):Iterate over the array with the right pointer expanding the window.
The right pointer moves forward to explore all possible subarrays, enabling the sliding window to grow and contract dynamically.
left = 0Initialize the left pointer of the sliding window to 0.
Starting the left pointer at 0 sets the initial boundary for the sliding window, enabling expansion from the start of the array.
longest = 0Initialize longest to record the maximum window size found.
This variable accumulates the length of the longest valid subarray encountered during iteration.
Test Your Understanding
Why does the algorithm subtract one from the maximum window size before returning the result?
Because the problem requires deleting exactly one element, the maximum window size found includes that element; subtracting one accounts for the deletion, yielding the length of the longest subarray of 1s after removing one element.
Related Problems
Sliding Window pattern
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