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.
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; }}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.