This is our solution and implementation to problem #1493: Longest Subarray of 1's After Deleting One Element on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Longest Subarray of 1's After Deleting One Element on LeetCode.
Problem Analysis
We are given an array nums where every element is a 0 or 1. We need to find the length of the longest consecutive sequence of 1s where one element is removed. If nums does not have any element which is not a 1, we must still remove one of the elements and return the corresponding count, which would be nums.length - 1. The naive approach would be to use two loops, one of which is nested, find each non-1 element, and scan ahead. This would have a time complexity of O(n^2) and thus would be inefficient for this problem, since solutions in O(n) do exist. We can use some additional space to improve the time complexity.
An improved implementation, which uses O(n) space and time, is to iterate through the input array once, store the indices of each non-1 value in a separate array nonOneIndices, then iterate over that array starting with the item at index 2, compare the differences between every other element, and return the greatest difference. The algorithm can be summarized as:
- Create the list of indices nonOneIndices.
- Add -1 as an index. This is not a real index but will be convenient to have for later steps.
- Iterate through nums, and for each non-1 value, add that index to nonOneIndicess.
- Add nums.length as an index to nonOneIndices. This is also not a real index but is done for convenience.
- Initialize an int bestDiff to 0.
- Iterate through nonOneIndices starting with i=2:
- Initialize an int diff to nonOneIndices[i] - nonOneIndices[i - 2] - 2.
- If diff > bestDiff, set bestDiff to diff.
- Return bestDiff.
In the implementation above, the -2 subtraction is done so we don't include the current index and the comparison index as part of the chain of 1s. We use i and i-2 and skip over i-1 to account for the deletion of one element. This is an improvement over the quadratic iteration approach, but we can simplify it further to reduce the space complexity to O(1). We'll outline this process below.
Implementation Strategy
Instead of creating a separate array of indices and iterating over that after the initial iteration, we can accomplish everything within the first iteration using two variables: lastNonOneIndex to record the previous index where the value is not 1, and prevLastNonOneIndex to record the previous index to that. Then, during iteration, when nums[i] != 1, perform the logic of taking the difference as described above and upate bestDiff if we've found something better. The full algorithm can be summarized as:
- Initialize ints lastNonOneIndex and prevLastNonOneIndex and set both to -1.
- Iterate through nums. For each value which is not 1:
- Initialize an int diff to i - prevLastNonOneIndex - 2.
- If diff > bestDiff, set bestDiff to diff.
- Set prevLastNonOneIndex to the value of lastNonOneIndex.
- Set lastNonOneIndex to the value of i.
- Perform one last check to see if nums.length - prevLastNonOneIndex - 2 is larger than bestDiff. Return the largest value.
These steps accomplish the same goal without the need of an array which can grow as the input grows.
Space and Time Complexity
The space complexity is O(1) as we are only using a constant number of variables throughout the iteration. The time complexity is O(n) as we will be visiting each element in the input exactly once.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.