Sponsored
Sponsored
This approach involves iterating through the array and counting the length of contiguous segments of zeros. For each segment of zeros with length n, the total number of zero-filled subarrays is the sum of the first n natural numbers.
For a segment with length n, the number of zero-filled subarrays is (n * (n + 1)) / 2. This formula is derived from the well-known sum formula for the first n integers.
Time Complexity: O(n), where n is the size of the input array. This is because we only traverse the array once.
Space Complexity: O(1), since we only use a constant number of extra variables.
1public class Solution {
2 public long ZeroFilledSubarray(int[] nums) {
3 int count = 0;
4 long subarrayCount = 0;
5 foreach (int num in nums) {
6 if (num == 0) {
7 count++;
8 } else {
9 count = 0;
10 }
11 subarrayCount += count;
12 }
13 return subarrayCount;
14 }
}C# uses a foreach loop to walk through the array, mimicking the logic of earlier languages to tally up zeros and add to the subarray count appropriately.
This approach is slightly variation. We keep track of the number of zero subarrays as we proceed through the array. Whenever a zero is encountered, the count of zero subarrays ending at that position is incremented by the number of zero subarrays ending at the previous position plus one. When a non-zero is encountered, we reset our counter.
Time Complexity: O(n) - traversing each element once to compute the solution.
Space Complexity: O(1) - using only a few extra integer variables for tracking.
public long ZeroFilledSubarray(int[] nums) {
long count = 0;
int zeroEndsHere = 0;
foreach (int num in nums) {
if (num == 0) {
zeroEndsHere++;
count += zeroEndsHere;
} else {
zeroEndsHere = 0;
}
}
return count;
}
}In C#, cumulative additions to zeroEndsHere bolster count, toggling the segment tracer for contiguous zeros as required.