Number of Zero-Filled Subarrays

Number of Zero-Filled Subarrays

What is this problem about?

The Number of Zero-Filled Subarrays problem asks you to count all subarrays that consist entirely of zeros. This coding problem applies the same run-length triangular number technique as "Number of Substrings With Only 1s" — for a run of L consecutive zeros, there are L*(L+1)/2 all-zero subarrays. The array and math interview pattern is demonstrated with the incremental run-count approach.

Why is this asked in interviews?

Microsoft, Meta, Amazon, and Google ask this as a warm-up problem that tests whether candidates recognize the triangular number pattern for runs of identical elements. The incremental count approach (adding run length to total at each step) is cleaner than computing formula per run.

Algorithmic pattern used

Incremental run tracking. For each index i: if arr[i] == 0, run = prev_run + 1. Else, run = 0. Add run to total count. Return total. This correctly counts 1 + 2 + ... + L = L*(L+1)/2 for each run of L zeros, accumulated incrementally.

Example explanation

arr=[0,0,1,0,0,0]. Process:

• i=0 (0): run=1. Total=1.
• i=1 (0): run=2. Total=3.
• i=2 (1): run=0. Total=3.
• i=3 (0): run=1. Total=4.
• i=4 (0): run=2. Total=6.
• i=5 (0): run=3. Total=9. Answer = 9 (zero subarrays: [0]×3 single, [0,0]×2, [0,0,0]×1 from last run, [0] from first run).

Common mistakes candidates make

• Computing L*(L+1)/2 separately for each run (correct but more complex).
• Not resetting run to 0 on non-zero elements.
• Off-by-one: run starts at 1 for a zero element, not 0.
• Integer overflow for large arrays (result can be O(n²) — use long/int64).

Interview preparation tip

The incremental contribution pattern — "add current run length to total at each step" — automatically computes the triangular number sum for each run. This O(n) single-pass approach is cleaner than finding all runs and computing formulas. It extends to any "count subarrays of all identical elements" problem. Memorize this pattern: it's a common building block for array subarray counting.