1493. Longest Subarray of 1's After Deleting One Element
Problem Description
The problem presents a binary array nums
, comprised of 0
s and 1
s. The task is to find the size of the largest contiguous subarray of 1
s that could be obtained by removing exactly one element from the array. You are also informed that if there is no such subarray made up entirely of 1
s after removing an element, the function should return 0
.
Intuition
The intuition for solving this problem involves looking at each segment of 1
s as a potential candidate and checking the length we can obtain after removing an element. We want to maximize this length by strategically picking an element for removal. The key insight here is that if there are consecutive 1
s, removing one 1
does not impact the length of the subarray of 1
s on either side of it.
We can approach the solution by precomputing and storing the lengths of continuous 1
s at any index from the left and right directions separately. This is done in two linear scans using the left
and right
auxiliary arrays:
-
From Left to Right: Starting at the index
1
, if the previous element is1
, increment the value in theleft
array at the current index by1
plus the value at the previous index. This will give us the number of continuous1
s to the left of each index in the arraynums
. -
From Right to Left: Starting from the second to last index and going backwards, if the next element is
1
, increment the value in theright
array at the current index by1
plus the value at the next index. This gives the number of continuous1
s to the right of each index.
The final result, after having populated both left
and right
arrays, is the maximum sum of corresponding elements from left
and right
arrays across all indices. This effectively simulates the removal of one element (either a 1
or 0
) and joining the contiguous 1
s from both left and right sides. However, the result should be the length after the removal of one element, so another -1 is implicitly considered in the max operation [since we don't actually remove the element but calculate what the length would be as if we did].
By applying this method, we can find the longest subarray containing only 1
s after deleting exactly one element.
Learn more about Dynamic Programming and Sliding Window patterns.
Solution Approach
The solution to this problem relies primarily on dynamic programming to keep track of the length of continuous 1
s on both sides of each index in the array nums
.
Here is a breakdown of the implementation details:
-
Initialization: Two lists,
left
andright
, each of the same length asnums
, are created and initialized with zeroes. These lists will store the length of continuous1
s to the left and right of each index, respectively. -
Populating the
left
list: We start iterating over the arraynums
from the second element onwards (index1
because we consider0
as the base case which is already initialized to zero). For each indexi
, if the element at the previous index (i - 1
) is1
, we setleft[i]
toleft[i - 1] + 1
. Effectively, this records the length of a stretch of1
s ending at the current index. -
Populating the
right
list: We do a similar iteration, but this time from right to left, starting from the second-to-last element (indexn - 2
wheren
is the length ofnums
). For each indexi
, if the element at the next index (i + 1
) is1
, we setright[i]
toright[i + 1] + 1
. This captures the length of a stretch of1
s starting right after the current index. -
Finding the longest subarray: Once we have both
left
andright
lists populated, we iterate over all possible remove positions (these positions do not have to be1
; they can be0
as well, as we will merge stretches of1
s around them). For each index, we calculate the sum ofleft[i] + right[i]
, which approximates the length of the subarray of1
s if we removed the element at the current index. However, since we are supposed to actually remove an element to create the longest subsequence, the sum implicitly considers this by not adding an additional1
even though we are summing the lengths from both sides. -
Returning the result: The maximum value from these sums corresponds to the size of the longest subarray containing only
1
s after one deletion. This is found using themax()
function applied to the sums ofleft[i] + right[i]
for each indexi
.
The algorithm completes this in linear time with two passes through nums
, and the space complexity is governed by the two additional arrays left
and right
, which are linear in the size of the input array nums
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use an example to illustrate the solution approach.
Suppose the input binary array nums
is [1, 1, 0, 1, 1, 1, 0, 1, 1]
.
Step by Step Solution
-
Initialization:
We initialize two lists,left
andright
, with the same length asnums
.
left
:[0, 0, 0, 0, 0, 0, 0, 0, 0]
right
:[0, 0, 0, 0, 0, 0, 0, 0, 0]
-
Populating the
left
list:
We iterate from left to right over the arraynums
, starting from index 1.nums[1]
is1
, andnums[0]
is1
, soleft[1] = left[0] + 1 -> 0 + 1 = 1
.- As we continue,
left
becomes[0, 1, 0, 1, 2, 3, 0, 1, 2]
.
-
Populating the
right
list:
Iterating from right to left, starting from index 7.nums[7]
is1
, andnums[8]
is1
, soright[7] = right[8] + 1 -> 0 + 1 = 1
.- Continuing this process, the
right
list fills up as[2, 1, 0, 4, 3, 2, 0, 1, 0]
.
-
Finding the longest subarray:
We calculate the potential longest subarrays after a deletion for each index, by summing theleft
andright
values at each index.- At index
2
(the first0
), the sum isleft[2] + right[2] = 0 + 0 = 0
. - At index
6
(the second0
), the sum isleft[6] + right[6] = 3 + 0 = 3
. - The longest subarray occurs at either index
2
or6
, where we would be removing the0
to join the1
s. - Considering every index, we would have sums as
[2, 1, 4, 5, 3, 2, 4, 1, 2]
.
- At index
-
Returning the result:
The maximum value from the sum ofleft
andright
for all indexes gives us the result.
In this case, the maximum is 5, corresponding to index3
. Thus, the size of the longest subarray containing only1
s after one deletion is5
.
This approach allows us to solve the problem with a single pass for left
and another for right
, totaling linear time complexity, O(n), with n
being the number of elements in nums
. The use of the two lists left
and right
gives us a space complexity of O(n) as well.
Solution Implementation
1from typing import List
2
3class Solution:
4 def longestSubarray(self, nums: List[int]) -> int:
5 # Determine the length of the nums list
6 n = len(nums)
7
8 # Initialize two lists to keep track of consecutive ones to the left and right of each index
9 left_ones_count = [0] * n
10 right_ones_count = [0] * n
11
12 # Calculate the consecutive ones to the left of each index
13 for i in range(1, n):
14 if nums[i - 1] == 1:
15 left_ones_count[i] = left_ones_count[i - 1] + 1
16
17 # Calculate the consecutive ones to the right of each index
18 for i in range(n - 2, -1, -1):
19 if nums[i + 1] == 1:
20 right_ones_count[i] = right_ones_count[i + 1] + 1
21
22 # Find the maximum length subarray formed by summing up counts of left and right ones.
23 # Note that the question assumes we can remove one zero to maximize the length.
24 # So, connecting two streaks of ones effectively means removing one zero between them.
25 max_length = max(a + b for a, b in zip(left_ones_count, right_ones_count))
26
27 return max_length
28
1class Solution {
2
3 // Function to find the length of the longest subarray consisting of 1s after deleting exactly one element.
4 public int longestSubarray(int[] nums) {
5 int length = nums.length;
6
7 // Arrays to store the count of consecutive 1s to the left and right of each index in nums
8 int[] leftOnesCount = new int[length];
9 int[] rightOnesCount = new int[length];
10
11 // Count consecutive 1s from left to right, starting from the second element
12 for (int i = 1; i < length; ++i) {
13 if (nums[i - 1] == 1) {
14 // If the previous element is 1, increment the count
15 leftOnesCount[i] = leftOnesCount[i - 1] + 1;
16 }
17 }
18
19 // Count consecutive 1s from right to left, starting from the second-to-last element
20 for (int i = length - 2; i >= 0; --i) {
21 if (nums[i + 1] == 1) {
22 // If the next element is 1, increment the count
23 rightOnesCount[i] = rightOnesCount[i + 1] + 1;
24 }
25 }
26
27 // Variable to store the answer, the maximum length of a subarray
28 int maxSubarrayLength = 0;
29
30 // Loop to find the maximum length by combining the left and right counts of 1s
31 for (int i = 0; i < length; ++i) {
32 // Compute the length of subarray by removing the current element, hence adding left and right counts of 1s.
33 // Since one element is always removed, the combined length of consecutive 1s from left and right
34 // should not be equal to the total length of the array (which implies no 0 was in the array to begin with).
35 maxSubarrayLength = Math.max(maxSubarrayLength, leftOnesCount[i] + rightOnesCount[i]);
36 }
37
38 // Reduce the length by 1 if the length of consecutive 1s equals the array length, since we need to remove one element.
39 if (maxSubarrayLength == length) {
40 maxSubarrayLength--;
41 }
42
43 // Return the maximum length of subarray after deletion
44 return maxSubarrayLength;
45 }
46}
47
1class Solution {
2public:
3 int longestSubarray(vector<int>& nums) {
4 // Get the size of the input array
5 int size = nums.size();
6
7 // Create two vectors to keep track of consecutive 1's on the left and right
8 vector<int> left(size, 0);
9 vector<int> right(size, 0);
10
11 // Fill the left array with the counts of consecutive 1's from the left
12 for (int i = 1; i < size; ++i) {
13 if (nums[i - 1] == 1) {
14 left[i] = left[i - 1] + 1;
15 }
16 }
17
18 // Fill the right array with the counts of consecutive 1's from the right
19 for (int i = size - 2; i >= 0; --i) {
20 if (nums[i + 1] == 1) {
21 right[i] = right[i + 1] + 1;
22 }
23 }
24
25 // Initialize the variable to store the maximum length of the subarray
26 int max_length = 0;
27
28 // Iterate over the input array to compute the maximum subarray length
29 for (int i = 0; i < size; ++i) {
30 // The longest subarray is the sum of consecutive 1's to the left and right of the current element
31 max_length = max(max_length, left[i] + right[i]);
32 }
33
34 // Return the computed maximum subarray length
35 return max_length;
36 }
37};
38
1function longestSubarray(nums: number[]): number {
2 // Get the size of the input array
3 const size: number = nums.length;
4
5 // Create two arrays to keep track of consecutive 1's to the left and right
6 let left: number[] = new Array(size).fill(0);
7 let right: number[] = new Array(size).fill(0);
8
9 // Fill the left array with the counts of consecutive 1's from the left
10 for (let i = 1; i < size; i++) {
11 if (nums[i - 1] === 1) {
12 left[i] = left[i - 1] + 1;
13 }
14 }
15
16 // Fill the right array with the counts of consecutive 1's from the right
17 for (let i = size - 2; i >= 0; i--) {
18 if (nums[i + 1] === 1) {
19 right[i] = right[i + 1] + 1;
20 }
21 }
22
23 // Initialize the variable to store the maximum length of the subarray
24 let maxLength: number = 0;
25
26 // Iterate over the input array to compute the maximum subarray length
27 for (let i = 0; i < size; i++) {
28 // The longest subarray is the sum of consecutive 1's to the left and right of the current element
29 maxLength = Math.max(maxLength, left[i] + right[i]);
30 }
31
32 // Return the computed maximum subarray length
33 return maxLength;
34}
35
Time and Space Complexity
The given code aims to find the length of the longest subarray of 1s after deleting one element from the array. Here's the analysis of its computational complexity:
Time Complexity:
-
The time complexity of this algorithm is
O(n)
, wheren
is the length of the input arraynums
. The reasoning behind this is that there are two separate for loops that each iterate over the array exactly once. The first loop starts from index 1 and goes up ton-1
, incrementing by 1 on each iteration. The second loop starts fromn-2
and goes down to 0, decrementing by 1 on each iteration. In both of these loops, only a constant amount of work is done (simple arithmetic and array accesses), so the time complexity for each loop is linear with respect to the size of the array. -
Furthermore, there's a final step that combines the results of the left and right arrays using
max
andzip
, which is also a linear operation since it involves a single pass over the combined arrays, making itO(n)
.
Adding up these linear time operations (3 * O(n)
) still results in an overall time complexity of O(n)
.
Space Complexity:
-
The space complexity of this algorithm is
O(n)
as well. This is because two additional arrays,left
andright
, are created to store the lengths of continuous ones to the left and right of each index, respectively. Each of these arrays is the same length as the input arraynums
. -
Besides the two arrays
left
andright
, there are only a constant number of variables used (i.e.,n
,i
,a
,b
), so they do not add more thanO(1)
to the space complexity.
Thus, the total space complexity is determined by the size of the two additional arrays, which gives us O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.