Longest Subarray of 1's After Deleting One Element - Video Solutions
Longest Subarray of 1's After Deleting One Element- Leetcode 1493 - Python
Longest Subarray of 1's After Deleting One Element - Video Solution
Watch 10 video solutions for Longest Subarray of 1's After Deleting One Element, a medium level problem involving Array, Dynamic Programming, Sliding Window. This walkthrough by TechError has 8,139 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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. |