Number of Zero-Filled Subarrays
Understanding the Problem
We need to count every contiguous subarray that consists entirely of zeros. A single 0 counts as one subarray. Two consecutive zeros give us three subarrays: [0] at the first position, [0] at the second position, and [0,0] spanning both. Three consecutive zeros give us six: three singles, two pairs, and one triple.
A run of k consecutive zeros produces k*(k+1)/2 zero-filled subarrays, because we can pick any start and end within the run, and the number of ways to do that is the sum 1 + 2 + 3 + ... + k. Non-zero elements never belong to a zero-filled subarray, so they split the array into independent runs. The total answer is the sum of k*(k+1)/2 over every maximal run of zeros.
Key Constraints:
1 <= nums.length <= 10^5→ With up to 100,000 elements, we need O(n) or O(n log n) at most. An O(n^2) brute force risks TLE.-10^9 <= nums[i] <= 10^9→ Values can be negative, positive, or zero. Only zeros matter for the count, so the actual magnitudes are irrelevant.- Return type is
long→ A run of 10^5 zeros produces 10^5 (10^5 + 1) / 2 = ~5 10^9 subarrays, which overflows a 32-bit integer. We need a 64-bit integer for the result.
Approach 1: Brute Force
Intuition
For every index that contains a zero, extend a subarray to the right as long as the elements stay zero. Each valid extension is another zero-filled subarray to count. This directly enumerates every zero-filled subarray by its starting position. It is correct but too slow for the largest inputs.
Algorithm
- Initialize a counter
countto 0. - For each index
ifrom 0 to n-1: - If
nums[i]is not 0, skip it. - Otherwise, starting from
i, extend right while elements are 0. - For each position
jyou reach (includingiitself), incrementcountby 1. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n^2). In the worst case (all zeros), the outer loop runs n times and the inner loop also runs up to n times, giving us O(n^2) total iterations.
- Space Complexity: O(1). We only use a single counter variable regardless of input size.
The brute force re-scans overlapping ranges for each starting zero. The next approach removes that repetition by counting, in a single pass, how many new subarrays each zero contributes based on its position within the current run.
Approach 2: Counting Consecutive Zeros (Optimal)
Intuition
Instead of recounting overlapping subarrays, count what each zero contributes on its own: how many new zero-filled subarrays end at this position.
- The first zero in a run contributes 1 subarray (itself).
- The second consecutive zero contributes 2 subarrays:
[0](itself) and[0,0](paired with the previous zero). - The third consecutive zero contributes 3:
[0],[0,0], and[0,0,0].
The k-th consecutive zero contributes exactly k new subarrays, so a running counter of consecutive zeros is enough. A non-zero element breaks the run and resets the counter to 0. At each step, add the current counter value to the total.
Every zero-filled subarray has exactly one rightmost element, so grouping subarrays by their ending position counts each one once with no double-counting. A subarray ending at position i is all zeros precisely when positions i, i-1, ..., i-k+1 are all zero, where k is the run length up to i. There are exactly k such subarrays (lengths 1 through k), which is the value consecutiveZeros holds at step i.
Summing these per-position contributions gives 1 + 2 + ... + k = k*(k+1)/2 for a run of length k, matching the closed-form count. The incremental counter computes that sum across the whole array in one pass.
Algorithm
- Initialize
countto 0 andconsecutiveZerosto 0. - For each element in
nums: - If the element is 0, increment
consecutiveZerosby 1. - Otherwise, reset
consecutiveZerosto 0. - Add
consecutiveZerostocount. - Return
count.
Example Walkthrough
Code
- Time Complexity: O(n). We make a single pass through the array, doing O(1) work per element.
- Space Complexity: O(1). We only use two variables (
countandconsecutiveZeros) regardless of input size.