AlgoMaster Logo

Number of Zero-Filled Subarrays

Last Updated: April 2, 2026

medium
3 min read

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.

Notice the pattern? A run of k consecutive zeros produces k*(k+1)/2 zero-filled subarrays. That's 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.

This observation is the key to solving the problem efficiently.

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 our 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

The most direct way to solve this: for every index that contains a zero, try extending a subarray to the right as long as the elements are still zero. Each valid extension is another zero-filled subarray to count.

This is what you'd naturally try first. It's simple and correct, just not fast enough for the largest inputs.

Algorithm

  1. Initialize a counter count to 0.
  2. For each index i from 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 j you reach (including i itself), increment count by 1.
  3. Return count.

Example Walkthrough

1Initialize: count = 0. Scan the array left to right.
0
1
1
3
2
0
3
0
4
2
5
0
6
0
7
4
1/9

Code

The brute force re-scans overlapping ranges for each starting zero. What if instead of recounting from each starting point, we figured out 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, think about what each zero contributes individually.

When you encounter a zero, ask: how many new zero-filled subarrays end at this position?

  • If it's the first zero in a run, it contributes 1 subarray (just itself).
  • If it's the second consecutive zero, it contributes 2 subarrays: [0] (itself) and [0,0] (paired with the previous zero).
  • If it's the third consecutive zero, it contributes 3: [0], [0,0], and [0,0,0].

So the pattern is: the k-th consecutive zero contributes exactly k new subarrays. All we need is a running counter of consecutive zeros.

When we hit a non-zero element, the run breaks and we reset the counter to 0. At each step, we add the current counter value to our total.

Algorithm

  1. Initialize count to 0 and consecutiveZeros to 0.
  2. For each element in nums:
    • If the element is 0, increment consecutiveZeros by 1.
    • Otherwise, reset consecutiveZeros to 0.
    • Add consecutiveZeros to count.
  3. Return count.

Example Walkthrough

1Initialize: count = 0, consecutiveZeros = 0
0
1
1
3
2
0
3
0
4
2
5
0
6
0
7
4
1/9

Code