Number of Zero-Filled Subarrays
MedPrompt
Given an integer array nums, return the number of subarrays filled with 0.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation:
There are 4 occurrences of [0] as a subarray.
There are 2 occurrences of [0,0] as a subarray.
There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.Example 2:
Input: nums = [0,0,0,2,0,0]
Output: 9
Explanation:
There are 5 occurrences of [0] as a subarray.
There are 3 occurrences of [0,0] as a subarray.
There is 1 occurrence of [0,0,0] as a subarray.
There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.Example 3:
Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through all possible subarrays, checking if each one is filled with zeros, and counting them. We can use two nested loops. The outer loop fixes the starting point of a subarray, and the inner loop extends the subarray to the right, counting valid zero-filled subarrays as it goes.
Algorithm
- Initialize a
longvariablecountto0to store the total number of zero-filled subarrays. - Use a nested loop structure. The outer loop iterates from
i = 0ton-1, wherenis the length of the array. The indexirepresents the starting point of a subarray. - The inner loop iterates from
j = iton-1. The indexjrepresents the ending point of the subarray. - For each subarray defined by
[i, j], check if the elementnums[j]is0. - If
nums[j]is0, it means the subarray fromitojconsists only of zeros (because all previous elements fromitoj-1must also have been zero for the inner loop to continue this far). Increment thecount. - If
nums[j]is not0, it means the current subarray and any subsequent subarrays starting aticannot be zero-filled. Therefore,breakthe inner loop and proceed to the next starting indexi+1. - After both loops complete, return the final
count.
Walkthrough
The brute-force method systematically checks every possible contiguous subarray within the input array nums. We can implement this using two nested loops. The outer loop, with index i, selects the starting element of the subarray. The inner loop, with index j, extends the subarray from i to j.
For each starting position i, we iterate from j = i onwards. If nums[j] is 0, we have found a valid zero-filled subarray nums[i...j], so we increment our total count. If we encounter a non-zero element at nums[j], we know that no subarray starting at i and ending at or after j can be zero-filled. This allows us to break the inner loop and move to the next starting position i+1, providing a slight optimization over a naive three-loop approach.
class Solution { public long zeroFilledSubarray(int[] nums) { long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { // Start a new potential subarray at index i for (int j = i; j < n; j++) { // Extend the subarray to index j if (nums[j] == 0) { // If nums[j] is 0, the subarray nums[i...j] is valid count++; } else { // If we find a non-zero, no more valid subarrays can start at i break; } } } return count; }}While straightforward, this approach is computationally expensive as it re-evaluates parts of the array multiple times.
Complexity
Time
O(n^2), where `n` is the length of the `nums` array. In the worst-case scenario, such as an array filled entirely with zeros, the inner loop runs `n-i` times for each `i`. This results in a total number of operations proportional to `n + (n-1) + ... + 1`, which is `n * (n+1) / 2`, leading to a quadratic time complexity.
Space
O(1), as we only use a constant amount of extra space for loop indices and the counter.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the definition of a subarray.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints (
n <= 10^5).
A much more efficient approach is to iterate through the array just once. We can count the number of zero-filled subarrays by keeping track of the length of the current contiguous sequence of zeros. The key insight is that a new zero at index i which extends a sequence of k-1 zeros to a sequence of k zeros, adds k new subarrays (all subarrays ending at i).
Algorithm
- Initialize two
longvariables:totalCount = 0to store the final result andconsecutiveZeros = 0to track the length of the current contiguous block of zeros. - Iterate through each number
numin the input arraynums. - If
numis0, incrementconsecutiveZeros. - If
numis not0, it means the block of zeros has ended, so resetconsecutiveZerosto0. - In each step of the iteration (regardless of whether the number is zero or not), add the current value of
consecutiveZerostototalCount. - After iterating through the entire array, return
totalCount.
Walkthrough
This optimal method avoids nested loops by processing the array in a single pass. The core idea is to count the length of the current contiguous sequence of zeros and accumulate the subarray counts on the fly.
We maintain a variable, consecutiveZeros, to track the length of the current streak of zeros. We iterate through the array. When we encounter a 0, we increment consecutiveZeros. This new zero creates consecutiveZeros new subarrays that end at the current position. For example, if we see a third consecutive zero, it creates the subarrays [0,0,0], [0,0], and [0] that end at its position. So, we add the current consecutiveZeros count to our totalCount.
When we encounter a non-zero number, the streak is broken, so we reset consecutiveZeros to 0. We still add consecutiveZeros (which is now 0) to the total, which has no effect.
This way, for any contiguous block of k zeros, we end up adding 1 + 2 + ... + k to the total count, which correctly calculates the number of subarrays k * (k + 1) / 2 for that block. The total count variable must be a long to prevent overflow, as the result can be large.
class Solution { public long zeroFilledSubarray(int[] nums) { long totalCount = 0; long consecutiveZeros = 0; for (int num : nums) { if (num == 0) { // We found a zero, extend the current sequence consecutiveZeros++; } else { // The sequence of zeros is broken consecutiveZeros = 0; } // Add the number of new subarrays ending at the current position totalCount += consecutiveZeros; } return totalCount; }}Complexity
Time
O(n), where `n` is the length of the `nums` array. This is because we perform a single pass through the array.
Space
O(1), as we only use a constant number of variables to store the counts, regardless of the input size.
Trade-offs
Pros
Extremely efficient with a linear time complexity, making it suitable for large inputs.
Optimal solution as it processes each element only once.
Requires minimal extra space.
The implementation is concise and elegant.
Cons
The logic, while simple, might be slightly less intuitive at first glance compared to the brute-force approach. It relies on the insight that the number of new subarrays ending at the current position is equal to the length of the current zero sequence.
Solutions
Solution
class Solution {public long zeroFilledSubarray(int[] nums) { long ans = 0; int cnt = 0; for (int v : nums) { cnt = v != 0 ? 0 : cnt + 1; ans += cnt; } return ans; }}class Solution {public: long long zeroFilledSubarray(vector<int> &nums) { long long ans = 0; int cnt = 0; for (int &v : nums) { cnt = v ? 0 : cnt + 1; ans += cnt; } return ans; }};class Solution: def zeroFilledSubarray(self, nums: List[int]) -> int: ans = cnt = 0 for v in nums: cnt = 0 if v else cnt + 1 ans += cnt return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.