Back to solutions

Number of Zero-Filled Subarrays

MediumArrays

Count contiguous subarrays consisting only of zeros.

Open problem
Constraints
  • 1 <= n <= 10^5
  • -10^9 <= nums[i] <= 10^9

Running run length

Time O(n)Space O(1)

Track the length of the current run of zeros. Each time you extend a run to length L, exactly L new zero-only subarrays end at this position, so add L to the total. A non-zero resets the run to 0.

Key terms
run:
A maximal consecutive stretch of zeros.
ending here count:
The number of zero subarrays that finish at the current index, equal to the run length.
long long zeroFilledSubarray(vector<int>& nums) {
    long long total = 0, run = 0;
    for (int x : nums) {
        if (x == 0) { run++; total += run; }
        else run = 0;
    }
    return total;
}
Step by step
  1. Keep run = 0 and total = 0.
  2. For each value: if it is 0, increment run and add run to total.
  3. If it is non-zero, reset run to 0.
  4. Return total. This implicitly sums L*(L+1)/2 over each run.