Longest Subarray of 1's After Deleting One Element
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It iterates through each element of the array, considering it for deletion. For each potential deletion, it scans the rest of the array to find the length of the longest subarray of consecutive 1s. The maximum length found across all possible deletions is the final answer.
Algorithm
- Initialize a variable
maxLengthto 0. - Iterate through each index
ifrom 0 ton-1, wherenis the length ofnums. - For each
i, simulate the deletion ofnums[i]. - Find the length of the longest subarray of 1s in the array after the simulated deletion.
a. Initialize
currentLength = 0andmaxInTemp = 0. b. Iterate through the array fromj = 0ton-1. c. Ifjis the index to be deleted (j == i), skip it. d. Ifnums[j]is 1, incrementcurrentLength. e. Ifnums[j]is 0, it breaks the sequence of 1s. UpdatemaxInTemp = Math.max(maxInTemp, currentLength)and resetcurrentLengthto 0. f. After the inner loop, perform one final update:maxInTemp = Math.max(maxInTemp, currentLength). - Update the overall
maxLengthwith the result from the current deletion:maxLength = Math.max(maxLength, maxInTemp). - After iterating through all possible deletions, return
maxLength.
Walkthrough
The brute-force method involves a nested loop structure. The outer loop selects an element to delete, and the inner loop calculates the longest run of 1s in the resulting array. This process is repeated for every element in the input array. While straightforward and easy to understand, its performance degrades significantly as the size of the input array increases.
class Solution { public int longestSubarray(int[] nums) { int n = nums.length; int maxLength = 0; for (int i = 0; i < n; i++) { // Simulate deleting nums[i] int currentLength = 0; int maxInTemp = 0; for (int j = 0; j < n; j++) { if (i == j) continue; // Skip the deleted element if (nums[j] == 1) { currentLength++; } else { maxInTemp = Math.max(maxInTemp, currentLength); currentLength = 0; } } maxInTemp = Math.max(maxInTemp, currentLength); maxLength = Math.max(maxLength, maxInTemp); } return maxLength; }}Complexity
Time
O(N^2), where N is the length of `nums`. The outer loop runs N times, and for each iteration, the inner loop also runs N times.
Space
O(1) extra space, as we are not creating new arrays but using indices to simulate deletion.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the logic of the problem statement.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' error on competitive programming platforms for the given constraints.
A more optimized approach involves pre-calculating information to avoid redundant computations. We can determine, for each position, the length of consecutive 1s ending just before it and starting just after it. By deleting a 0 at a given position, we can merge these two segments of 1s. The maximum possible merged length is our answer.
Algorithm
- Create two integer arrays,
leftandright, of the same size asnums. - Populate the
leftarray: Iterate from left to right.left[i]will store the count of consecutive 1s ending at indexi. Ifnums[i]is 0,left[i]is 0. Otherwise,left[i] = (i > 0 ? left[i-1] : 0) + 1. - Populate the
rightarray: Iterate from right to left.right[i]will store the count of consecutive 1s starting at indexi. Ifnums[i]is 0,right[i]is 0. Otherwise,right[i] = (i < n-1 ? right[i+1] : 0) + 1. - Initialize
maxLength = 0and a booleanhasZero = false. - Iterate through the array from
i = 0ton-1. Ifnums[i]is 0, it means we can potentially merge the subarray of 1s to its left and the one to its right. a. SethasZero = true. b. Calculate the length of the left part:leftOnes = (i > 0) ? left[i-1] : 0. c. Calculate the length of the right part:rightOnes = (i < n-1) ? right[i+1] : 0. d. UpdatemaxLength = Math.max(maxLength, leftOnes + rightOnes). - After the loop, if
hasZerois true, it means we found at least one 0 andmaxLengthholds the answer. IfhasZerois false, it means the array consists of all 1s. Since we must delete one element, the answer isn-1.
Walkthrough
This method uses a dynamic programming-like strategy. We use two auxiliary arrays, left and right. left[i] stores the length of the consecutive sequence of 1s ending at index i, and right[i] stores the length of the consecutive sequence of 1s starting at index i. After populating these two arrays in two separate linear passes, we can find the solution in a third pass. For each index i where nums[i] is 0, we can find the length of the resulting subarray of 1s by summing left[i-1] and right[i+1]. We take the maximum of these sums over all possible 0s to delete. A special case is when the array contains no zeros; in this scenario, we must delete a 1, so the answer is simply the array length minus one.
class Solution { public int longestSubarray(int[] nums) { int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; for (int i = 0; i < n; i++) { if (nums[i] == 1) { left[i] = (i > 0 ? left[i - 1] : 0) + 1; } } for (int i = n - 1; i >= 0; i--) { if (nums[i] == 1) { right[i] = (i < n - 1 ? right[i + 1] : 0) + 1; } } int maxLength = 0; boolean hasZero = false; for (int i = 0; i < n; i++) { if (nums[i] == 0) { hasZero = true; int leftOnes = (i > 0) ? left[i - 1] : 0; int rightOnes = (i < n - 1) ? right[i + 1] : 0; maxLength = Math.max(maxLength, leftOnes + rightOnes); } } return hasZero ? maxLength : n - 1; }}Complexity
Time
O(N), as it involves three separate linear passes over the array.
Space
O(N), for the `left` and `right` arrays used for pre-computation.
Trade-offs
Pros
Much more efficient than the brute-force approach with linear time complexity.
The logic is systematic and breaks the problem down into smaller, pre-computable parts.
Cons
Requires extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
The most efficient solution uses the sliding window technique. The goal is to find the longest subarray that contains at most one zero. We maintain a window of elements, expand it to the right, and shrink it from the left whenever the condition (at most one zero) is violated. The size of this window minus one gives a candidate for the answer.
Algorithm
- Initialize
left = 0,zeroCount = 0, andmaxLength = 0. - Use a
rightpointer to iterate through the array from0ton-1, expanding a window[left, right]. - If
nums[right]is 0, incrementzeroCount. - The window is valid as long as it contains at most one zero (
zeroCount <= 1). IfzeroCountbecomes greater than 1, the window is invalid. - Shrink the window from the left by incrementing the
leftpointer until the window is valid again. While shrinking, ifnums[left]is a 0, decrementzeroCount. - For each valid window
[left, right], it represents a subarray with at most one 0. If we delete one element from this window, the longest possible subarray of 1s has length(right - left + 1) - 1, which simplifies toright - left. - Update
maxLength = Math.max(maxLength, right - left). - After the
rightpointer has traversed the entire array,maxLengthwill hold the answer.
Walkthrough
We use two pointers, left and right, to define the boundaries of our sliding window. We expand the window by moving right. We keep a count of zeros within the current window. If the count of zeros exceeds one, we must shrink the window from the left by moving the left pointer forward until the zero count is back to one. At each step, the window [left, right] is the longest subarray ending at right with at most one zero. The length of the subarray of 1s we can form from this window is its size minus one (for the single element we must delete). The size of the window is right - left + 1, so the length of the 1s subarray is right - left. We continuously update a maxLength variable with the maximum right - left value seen. This single-pass approach is optimal in both time and space.
class Solution { public int longestSubarray(int[] nums) { int n = nums.length; int left = 0; int zeroCount = 0; int maxLength = 0; for (int right = 0; right < n; right++) { if (nums[right] == 0) { zeroCount++; } // Shrink the window until it has at most one zero while (zeroCount > 1) { if (nums[left] == 0) { zeroCount--; } left++; } // The current window is [left, right] and contains at most one zero. // The length of the subarray of 1s we can form is window_size - 1. // window_size = right - left + 1. // So, length of 1s = (right - left + 1) - 1 = right - left. maxLength = Math.max(maxLength, right - left); } return maxLength; }}Complexity
Time
O(N), because each element is visited at most twice (once by the `right` pointer and once by the `left` pointer).
Space
O(1), as we only use a few constant extra variables for pointers and counts.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
It's a generalizable pattern applicable to many subarray problems.
Cons
The logic, while efficient, can be slightly less intuitive to grasp on the first look compared to more direct methods.
Solutions
Solution
class Solution {public int longestSubarray(int[] nums) { int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; for (int i = 1; i < n; ++i) { if (nums[i - 1] == 1) { left[i] = left[i - 1] + 1; } } for (int i = n - 2; i >= 0; --i) { if (nums[i + 1] == 1) { right[i] = right[i + 1] + 1; } } int ans = 0; for (int i = 0; i < n; ++i) { ans = Math.max(ans, left[i] + right[i]); } return ans; }}class Solution: def longestSubarray(self, nums: List[int]) -> int: n = len(nums) left = [0] * n right = [0] * n for i in range(1, n): if nums[i - 1] == 1: left[i] = left[i - 1] + 1 for i in range(n - 2, - 1, - 1): if nums[i + 1] == 1: right[i] = right[i + 1] + 1 return max(a + b for a, b in zip(left, right))class Solution {public: int longestSubarray(vector<int> &nums) { int n = nums.size(); vector<int> left(n); vector<int> right(n); for (int i = 1; i < n; ++i) { if (nums[i - 1] == 1) { left[i] = left[i - 1] + 1; } } for (int i = n - 2; ~i; --i) { if (nums[i + 1] == 1) { right[i] = right[i + 1] + 1; } } int ans = 0; for (int i = 0; i < n; ++i) { ans = max(ans, left[i] + right[i]); } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.