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.
1const longestSubarray = function(nums) {
2 let maxLen = 0, left = 0, zeroCount = 0;
3 for (let right = 0; right < nums.length; right++) {
4 if (nums[right] === 0) zeroCount++;
5 while (zeroCount > 1) {
6 if (nums[left] === 0) zeroCount--;
7 left++;
8 }
9 maxLen = Math.max(maxLen, right - left);
10 }
11 return maxLen;
12};
13
14// Usage Example
15console.log(longestSubarray([0,1,1,1,0,1,1,0,1]));The JavaScript implementation mirrors the logic of other languages, employing a two-pointer technique to dynamically adjust the count of zeros within the subarray being considered.
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 Python solution tactfully constructs and uses prefix and suffix tables to evaluate each point in the array methodically. It ensures complete use of subsections around a singular potential deletion point.