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.
1#include <stdio.h>
2
3int longestSubarray(int* nums, int numsSize) {
4 int maxLen = 0;
5 int zeroCount = 0;
6 int currentLen = 0, prevLen = 0;
7 for (int i = 0; i < numsSize; i++) {
8 if (nums[i] == 1) {
9 currentLen++;
10 } else {
11 maxLen = zeroCount == 0 ? currentLen : max(maxLen, prevLen + currentLen);
12 prevLen = currentLen;
13 currentLen = 0;
14 zeroCount++;
15 if (zeroCount > 1) zeroCount = 1;
16 }
17 }
18 maxLen = max(maxLen, prevLen + currentLen);
19 return maxLen == numsSize ? maxLen - 1 : maxLen;
20}
21
22int main() {
23 int nums[] = {0,1,1,1,0,1,1,0,1};
24 int size = sizeof(nums)/sizeof(nums[0]);
25 printf("%d", longestSubarray(nums, size));
26 return 0;
27}The C solution iterates through the array and calculates the length of subarrays of 1's using counters. It uses variables to keep track of the length before and after a zero, and updates the maximum length as needed. Edge cases are handled by checking if the current maximum length equals the size of the array, indicating every element is 1 and one must be deleted.
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 JavaScript function constructs and utilizes prefix and suffix tables, iterating in a subsequent loop to optimally calculate maximum subarray lengths by simulating removal of zero from the array strategically.