Longest Subarray of 1's After Deleting One Element - Solution & Explanation
Problem Statement
Given a binary array nums, you should delete one element from it.
Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.
Example 1:
Input: nums = [1,1,0,1] Output: 3 Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.
Example 2:
Input: nums = [0,1,1,1,0,1,1,0,1] Output: 5 Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].
Example 3:
Input: nums = [1,1,1] Output: 2 Explanation: You must delete one element.
Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
Approach Overview
Problem Overview: You receive a binary array and must delete exactly one element. After the deletion, return the length of the longest contiguous subarray containing only 1s. The challenge is maximizing the length while handling the single allowed deletion efficiently.
Approach 1: Sliding Window with Variables (O(n) time, O(1) space)
This approach uses the classic sliding window technique. Maintain two pointers left and right and track how many zeros exist inside the window. Expand the window by moving right. When more than one zero appears, shrink the window by moving left until only one zero remains. Since deleting one element effectively allows one zero inside the window, the maximum valid window length minus one represents the answer. The array is scanned once, making this approach linear and memory efficient.
Approach 2: Prefix Sum and Single Pass (O(n) time, O(n) space)
This method precomputes consecutive runs of ones using prefix-style arrays. One array stores the number of consecutive 1s ending at each index from the left, while another stores consecutive 1s starting from each index from the right. When a 0 appears, you simulate deleting it by combining the left and right counts: left[i-1] + right[i+1]. This effectively merges two blocks of ones separated by a zero. The algorithm performs a single pass to build the arrays and another to compute the best merge. It uses extra memory but clearly demonstrates the structure of the problem using ideas similar to dynamic programming over an array.
Recommended for interviews: The sliding window solution is what interviewers typically expect. It shows you understand how to maintain constraints dynamically while scanning the array once. The prefix approach demonstrates solid reasoning about prefix states and segment merging, but the sliding window version is simpler, uses constant space, and is easier to implement under interview pressure.
Approach 1: Sliding Window with Variables
This approach uses a sliding window technique with variables to keep track of the count of consecutive 1's before and after a zero. The main idea is to iterate through the array, and whenever you encounter more than one zero, calculate the length of 1's that can be formed by deleting the previous zero, update maximum length as needed, and reset counts.
The C solution iterates through the array and calculates the length of subarrays of 1's using counters. It uses variables to keep track of the length before and after a zero, and updates the maximum length as needed. Edge cases are handled by checking if the current maximum length equals the size of the array, indicating every element is 1 and one must be deleted.
Complexity
Time Complexity: O(n), as we iterate through the array once.
Space Complexity: O(1), as no additional space is used proportional to input size.
Approach 2: Prefix Sum and Single Pass
This approach utilizes prefix sums to keep a cumulative count of 1's encountered and calculates lengths avoiding excessive recalculations. Two arrays store the prefix sum of 1's up to the current element and from the current element to the end, respectively. A single pass is then made to compute the maximum length by checking possible deletions at each zero.
This C solution efficiently constructs a prefix and suffix table with cumulative counts of consecutive 1's. With these, every possible 0 is evaluated by checking adjacent blocks, optimizing overall calculations.
Complexity
Time Complexity: O(n), each element is processed three independent times.
Space Complexity: O(n), proportional to input due to prefix and suffix arrays.
Approach 3: Enumeration
We can enumerate each position i to be deleted, then calculate the number of consecutive 1s on the left and right, and finally take the maximum value.
Specifically, we use two arrays left and right of length n+1, where left[i] represents the number of consecutive 1s ending with nums[i-1], and right[i] represents the number of consecutive 1s starting with nums[i].
The final answer is max_{0 leq i < n} {left[i] + right[i+1]}.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
Approach 4: Two Pointers
The problem is actually asking us to find the longest subarray that contains at most one 0. The remaining length after deleting one element from this subarray is the answer.
Therefore, we can use two pointers j and i to point to the left and right boundaries of the subarray, initially j = 0, i = 0. In addition, we use a variable cnt to record the number of 0s in the subarray.
Next, we move the right pointer i. If nums[i] = 0, then cnt is incremented by 1. When cnt > 1, we need to move the left pointer j until cnt leq 1. Then, we update the answer, i.e., ans = max(ans, i - j). Continue to move the right pointer i until i reaches the end of the array.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Approach 5: Two Pointers (Optimization)
In Solution 2, we move the left pointer in a loop until cnt leq 1. Since the problem asks for the longest subarray, it means we don't need to reduce the length of the subarray. Therefore, if cnt \gt 1, we only move the left pointer once, and the right pointer continues to move to the right. This ensures that the length of the subarray does not decrease.
Finally, the answer we return is n - l - 1, where l is the position of the left pointer.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window with Variables | Time Complexity: O(n), as we iterate through the array once. |
| Prefix Sum and Single Pass | Time Complexity: O(n), each element is processed three independent times. |
| Enumeration | — |
| Two Pointers | — |
| Two Pointers (Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Variables | O(n) | O(1) | Best general solution. Optimal for interviews and large arrays due to constant space. |
| Prefix Sum and Single Pass | O(n) | O(n) | Useful when analyzing contiguous segments or when prefix information simplifies reasoning. |
Video Solution
Longest Subarray of 1's After Deleting One Element- Leetcode 1493 - Python • TechError • 8,139 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Subarray of 1's After Deleting One Element easy or hard?
Longest Subarray of 1's After Deleting One Element Python/Java solution
How to solve Longest Subarray of 1's After Deleting One Element in O(n)?
What is the best approach for Longest Subarray of 1's After Deleting One Element?
Is Longest Subarray of 1's After Deleting One Element asked at Google/Amazon/Meta?
What data structure is used in Longest Subarray of 1's After Deleting One Element?
What is the time complexity of Longest Subarray of 1's After Deleting One Element?
Ready to solve this problem?
Practice Longest Subarray of 1's After Deleting One Element with our built-in code editor and test cases.
Practice on FleetCode