Sponsored
Sponsored
This approach uses a sliding window technique with variables to keep track of the count of consecutive 1's before and after a zero. The main idea is to iterate through the array, and whenever you encounter more than one zero, calculate the length of 1's that can be formed by deleting the previous zero, update maximum length as needed, and reset counts.
Time Complexity: O(n), as we iterate through the array once.
Space Complexity: O(1), as no additional space is used proportional to input size.
1class Solution:
2 def longestSubarray(self, nums):
3 max_len = 0
4 left = 0
5 zero_count = 0
6
7 for right in range(len(nums)):
8 if nums[right] == 0:
9 zero_count += 1
10 while zero_count > 1:
11 if nums[left] == 0:
12 zero_count -= 1
13 left += 1
14 max_len = max(max_len, right - left)
15 return max_len
16
17# Usage
18# sol = Solution()
19# print(sol.longestSubarray([0,1,1,1,0,1,1,0,1]))The Python code iterates over the array with a window, counting zeros and ensuring the window only contains at most one zero for the desired result. Left pointer is incremented to adjust the window whenever more than one zero is encountered.
This approach utilizes prefix sums to keep a cumulative count of 1's encountered and calculates lengths avoiding excessive recalculations. Two arrays store the prefix sum of 1's up to the current element and from the current element to the end, respectively. A single pass is then made to compute the maximum length by checking possible deletions at each zero.
Time Complexity: O(n), each element is processed three independent times.
Space Complexity: O(n), proportional to input due to prefix and suffix arrays.
The Java code constructs prefix and suffix arrays in a straightforward pass, calculating the maximum available length in a final pass by considering subarrays formed on omitting a zero.