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 either 0 or 1.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.
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.
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.
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.
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 | 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. |
| 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. |
#leetcode 1493. Longest Subarray of 1's After Deleting One Element • Pavel Bukhtik • 40,121 views views
Watch 9 more video solutions →Practice Longest Subarray of 1's After Deleting One Element with our built-in code editor and test cases.
Practice on FleetCode