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.
Example 4:
Input: nums = [1,1,0,0,1,1,1,0,1] Output: 4
Example 5:
Input: nums = [0,0,0] Output: 0
Constraints:
1 <= nums.length <= 10^5nums[i] is either 0 or 1.
The description was taken from https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/.
#O(N) Time, O(1) Space
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
left, right = 0, 0
window, output = 0, 0
while right < len(nums):
window += nums[right]
right += 1
while window < right - left - 1:
window -= nums[left]
left += 1
output = max(output, right - left - 1)
return output
This problem is very similar to Minimum Swaps to Group All 1s Together.
In this problem, we are looking for a specific subarray. This subarray is a range where the sum of elements between the range and the range differ only by one.
If we are given a problem that requires searching for a contiguous sublist or substring, a sliding window is typically a good approach.
What we can do is have a running sum that will be incremented by the ones we have between a left and a right pointer, signifying our window. If we ever find that that running sum and our window varies by less than one, we will shrink it.
That is the general template for sliding window problems, we will expand the right side until our window is no longer valid in which case we will shrink the left. In this case, the window will no longer be valid if we have more than one zero within it.
Let's start by initializing our pointers to the beginning index of the array.
left, right = 0, 0
We'll also need a running window sum and an output variable to track the longest window we found that satisfied the given constraint.
window, output = 0, 0
Now let's begin traversing the string.
We will continue until the right pointer has gone past the end of the array.
while right < len(nums)
Just like other sliding window problems, our right pointer will be in charge of throwing values into the window. The left will be in charge of evicting values from it.
Let's throw the number at the right pointer into the window then expand.
window += nums[right]
right += 1
We can continue expanding until our window does not satisfy the given constraint, when we have more than two zeros within our window.
We'll know that is the case if the sum of the window is less than the size of the window, minus one.
While this continues to be the case, we will shrink the left side by removing the left number and incrementing the left pointer.
while window < right - left - 1:
window -= nums[left]
left += 1
Once we have made sure our window is of the given constraint, we will test it against the current longest window we have saved, updating our output if it is greater.
We'll need to subtract one from the size of the window since we are required to delete one index from the size no matter what.
output = max(output, right - left - 1)
After we have traversed the string, we will return the output which will be the longest subarray of ones after deleting one element.
return output