Number of Zero-Filled Subarrays
Medium · Arrays & Hashing · Array · Math
Problem
You are given an integer array nums. Return the number of subarrays whose elements are all 0.
A subarray is a contiguous, non-empty part of the array. Two subarrays at different positions count separately, even when they hold the same values.
Examples
Input: nums = [1,3,0,0,2,0,0,4] Output: 6
Each run of two zeros holds three subarrays: [0], [0] and [0,0]. 3 + 3 = 6.
Input: nums = [0,0,0,2,0,0] Output: 9
The run of three gives 3 + 2 + 1 = 6 and the run of two gives 3: 9 in all.
Input: nums = [2,10,2019] Output: 0
There are no zeros, so no subarray qualifies.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Approaches
- Extend from every start — time O(n + Z²), Z = zeros, space O(1)
Follow-up
The answer can reach 10^5 * (10^5 + 1) / 2, about 5 * 10^9, which does not fit in a 32-bit integer: use a 64-bit total in Java, C++ and Go. The same "add the run length at each step" pattern counts subarrays with any property that holds for every element on its own (all equal, all below a limit, all even).
Related problems
Start free on Cariara · Coding problems · System design studio
