Number of Zero-Filled Subarrays
Problem
nums, count how many contiguous,
non-empty subarrays consist only of zeros. Subarrays at different positions count
separately even if they look the same. The answer can exceed the int range,
so return a long.nums = [1,3,0,0,2,0,0,4]Output6 (four [0] + two [0,0])nums = [0,0,0,2,0,0]Output9 (run of 3 gives 6, run of 2 gives 3)nums = [2,10,2019]Output01 ≤ n ≤ 105 · -109 ≤ nums[i] ≤ 109
Try it yourself
class Solution {
public long zeroFilledSubarray(int[] nums) {
}
}
len, exactly len all-zero subarrays end here. Summing
the streak at every index gives the answer in one pass.Instinct "In place", "O(1) extra space" or "one pass" over an array? Think write pointer, reversal, prefix/suffix passes or using indices as storage.
Memory hack Read fast, write slow, reverse to rotate, and let the index be the hash.
Open the Array Manipulation guide →Approaches
Brute ForceEnumerate and Verify Every Subarray
O(n3)Space O(1)List every pair (i, j) and scan nums[i..j] to see
whether all entries are zero. It is the definition turned into code.
public long zeroFilledSubarray(int[] nums) { int n = nums.length; long count = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { boolean allZero = true; for (int k = i; k <= j && allZero; k++) { if (nums[k] != 0) allZero = false; } if (allZero) count++; } } return count; }
Directly mirrors the statement, but cubic time is far too slow.
BetterExtend from Each Start, Stop at a Non-Zero
O(n2)Space O(1)If nums[i..j] contains a non-zero, every longer subarray from
i does too. So from each start, extend j while the value
is zero, counting one subarray per step, and break at the first non-zero.
public long zeroFilledSubarray(int[] nums) { int n = nums.length; long count = 0; for (int i = 0; i < n; i++) { // nums[i..j] stays valid only while every new value is zero for (int j = i; j < n && nums[j] == 0; j++) { count++; } } return count; }
Drops the inner check, yet an all-zero array still costs n2/2 steps.
OptimalOne Pass — Add the Current Streak
O(n)Space O(1)Keep streak = number of consecutive zeros ending at index
i. Each of those zeros can start an all-zero subarray ending at
i, so add streak to the total. A non-zero resets it.
Equivalently, each run of length L contributes
L·(L+1)/2.
public long zeroFilledSubarray(int[] nums) { long count = 0; long streak = 0; // zeros ending at the current index for (int x : nums) { if (x == 0) { streak++; count += streak; // new subarrays that end here } else { streak = 0; } } return count; }
Dry runnums = [1,3,0,0,2,0,0,4]
- i=00i00200streak=1, count=1
- i=100i0200streak=2, count=3
- i=2000i200streak=3, count=6
- i=30002i00non-zero → streak=0
- i=400020i0streak=1, count=7
- i=5000200istreak=2, count=9 ✔
Linear, constant memory — nothing left to optimise.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Enumerate and Verify Every Subarray | O(n3) | O(1) |
| Better | Extend from Each Start, Stop at a Non-Zero | O(n2) | O(1) |
| Optimal | One Pass — Add the Current Streak | O(n) | O(1) |
- Returning
int— 105 zeros give ~5·109 subarrays, which overflows. - Counting only maximal runs (one per block) instead of every sub-run inside each block.
- Forgetting to reset the streak on a non-zero, which merges separate blocks.
- Do a tiny example by hand: a run of 3 zeros → 3 + 2 + 1 = 6 subarrays.
- Explain the “count by right end” view; it avoids any formula derivation.
- Call out the
longreturn type before the interviewer does.