Watch 10 video solutions for Number of Zero-Filled Subarrays, a medium level problem involving Array, Math. This walkthrough by NeetCodeIO has 16,204 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |