Number of Zero-Filled Subarrays — Medium Problem & Solution

Return the number of contiguous subarrays of nums in which every element is 0.

Difficulty: Medium
Topics: Arrays, Math, Counting
Asked at: Amazon, Google, Paytm
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the number of contiguous subarrays of nums in which every element is 0.

Example 1

Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
Explanation: Two runs of two zeros each contribute 3 subarrays.

Example 2

Input: nums = [0,0,0,2,0,0]
Output: 9
Explanation: A run of three gives 6 and a run of two gives 3.

Example 3

Input: nums = [2,10,2019]
Output: 0

Constraints

1 <= nums.length <= 1000
-1000000000 <= nums[i] <= 1000000000

How to solve Number of Zero-Filled Subarrays

Count by right endpoint. At each position that holds a zero, the number of all-zero subarrays ending there equals the length of the zero run ending there — so a single running counter gives the total.

Approach

Keep run, the length of the zero run ending at the current index.
On a zero, increment run; on anything else, reset it to 0.
Add run to the answer at every step.

Why it works

Summing the run length over the positions of a run of length L gives 1 + 2 + … + L = L(L+1)/2, which is exactly the number of subarrays inside it — and runs are disjoint, so the totals add.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Adding L * (L + 1) / 2 only when a run ends misses the run that reaches the end of the array unless you flush after the loop.
At the real LeetCode limits the answer exceeds 32 bits; this version caps the length at 1000 so it fits.

Reference solution

Python

from typing import List

def zeroFilledSubarray(nums: List[int]) -> int:
    total = run = 0
    for x in nums:
        run = run + 1 if x == 0 else 0
        total += run
    return total

JavaScript

var zeroFilledSubarray = function(nums) {
    var total = 0, run = 0;
    for (var i = 0; i < nums.length; i++) {
        run = nums[i] === 0 ? run + 1 : 0;
        total += run;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue