Longest Subarray Of 1s After Deleting One Element - Leetcode Solution

Problem statement:

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.

If there is no such subarray, return 0.

Solution:

Approach:

One approach could be to find all the subarrays where one element is deleted, and among those subarrays, the subarray having the longest consecutive ones is the answer.

For this, we can iterate over the given array nums and for each i, we can delete nums[i] and create a new array without it. Next, we can iterate over that new array and find the consecutive ones to calculate the maximum length subarray of 1s in it.

We can achieve this by maintaining the count of consecutive ones in a variable and resetting it to 0 whenever we encounter a 0. We can also maintain a variable maxLength to keep track of the maximum length subarray of 1s encountered so far.

We can return the maxLength as the answer.

Algorithm:

1. Initialize maxLength = 0
2. Iterate over nums for each index i: a. Create a new array by deleting nums[i] b. Initialize count and maxCount to 0 c. Iterate over the new array for each index j: i. If jth element is 1, increment count by 1 ii. If jth element is 0, reset count to 0 iii. Update maxCount to be the maximum of maxCount and count d. Update maxLength to be the maximum of maxLength and maxCount
3. Return maxLength

Python code:

class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: maxLength = 0 # iterate over nums for i in range(len(nums)): # create new array without nums[i] newArr = nums[:i] + nums[i+1:] count = maxCount = 0 # iterate over new array for j in range(len(newArr)): # if jth element is 1, increment count if newArr[j] == 1: count += 1 # if jth element is 0, reset count else: count = 0 # update maxCount to be maximum of count and maxCount maxCount = max(maxCount, count) # update maxLength to be the maximum of maxLength and maxCount maxLength = max(maxLength, maxCount) # return maxLength return maxLength

Time Complexity: O(N^2), where N is the length of the input array nums.

The time complexity of the algorithm is O(N^2) because for each i, we create a new array without nums[i], and then iterate over that new array, resulting in a nested loop.

Space Complexity: O(N), where N is the length of the input array nums.

The space complexity of the algorithm is O(N) because we create a new array without nums[i], resulting in additional space usage.

1