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] <= 109Problem Overview: Given an integer array nums, count how many subarrays contain only zeros. A valid subarray must consist entirely of 0 values and can be any contiguous portion of the array.
The key observation: zero-filled subarrays only come from contiguous blocks of zeros. If a block contains k zeros, it contributes multiple subarrays of different lengths.
Approach 1: Contiguous Zero Segment Counting (O(n) time, O(1) space)
Scan the array and identify contiguous segments of zeros. Suppose a segment contains k zeros. The number of subarrays that can be formed from that segment equals k * (k + 1) / 2. This works because each position can start a subarray and extend through the remaining zeros. For example, a run of 3 zeros produces subarrays: [0], [0], [0], [0,0], [0,0], and [0,0,0]. Iterate through the array, track the length of each zero run, compute the formula when the run ends, and add it to the total. This approach relies only on sequential traversal of the array and a simple combinatorial formula from math. Time complexity is O(n) because each element is visited once, and space complexity is O(1).
Approach 2: Running Zero Count Accumulation (O(n) time, O(1) space)
Instead of computing the contribution of a whole segment at once, accumulate it incrementally. Maintain a variable zeroCount representing the current streak of consecutive zeros. While iterating through the array, if the current value is zero, increment zeroCount and add it directly to the result. If the value is non‑zero, reset zeroCount to zero. The intuition: when you extend a zero streak, every new zero creates additional subarrays ending at the current index. For example, the third zero in a streak contributes three new subarrays ending there. This approach still performs a single pass through the array, but avoids explicitly calculating segment lengths. Time complexity remains O(n) with O(1) auxiliary space.
Recommended for interviews: The running accumulation approach is usually preferred. It shows you recognize how subarrays grow dynamically and can compute the result during iteration. The contiguous segment method also works and clearly demonstrates the combinatorial insight (k * (k + 1) / 2). In interviews, explaining the segment formula first and then implementing the running count version often shows stronger problem‑solving depth.
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.
The C solution iterates over the array, increasing the count for each contiguous zero encountered and adds the current count to the total subarrayCount anytime zeros[i] != 0 is encountered.
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.
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.
A variation of the simple count, where we keep another variable zeroEndsHere which tracks ongoing segments of zeros. This accumulates into count as the loop progresses.
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.
We traverse the array nums and use a variable cnt to record the current number of consecutive 0s. For the current element x we are traversing, if x is 0, then cnt is incremented by 1, and the number of all-zero subarrays ending with the current x is cnt, which we add to the answer. Otherwise, we set cnt to 0.
After the traversal, we return the answer.
Time complexity O(n), where n is the length of the array nums. Space complexity O(1).
Similar problems:
| Approach | Complexity |
|---|---|
| Approach 1: Count zero subarrays using a contiguous segments approach | Time Complexity: O(n), where Space Complexity: O(1), since we only use a constant number of extra variables. |
| Approach 2: Accumulative count of zero subarrays | 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. |
| Traversal and Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Contiguous Zero Segment Counting | O(n) | O(1) | When you want a clear mathematical explanation using the k*(k+1)/2 formula for each zero block |
| Running Zero Count Accumulation | O(n) | O(1) | Best for interviews and clean implementations that compute results during a single pass |
Number of Zero-Filled Subarrays - Leetcode 2348 - Python • NeetCodeIO • 16,204 views views
Watch 9 more video solutions →Practice Number of Zero-Filled Subarrays with our built-in code editor and test cases.
Practice on FleetCode