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.
This C solution efficiently constructs a prefix and suffix table with cumulative counts of consecutive 1's. With these, every possible 0 is evaluated by checking adjacent blocks, optimizing overall calculations.