Number of Zero-Filled Subarrays — Problem & Solution
Number of Zero-Filled Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Zero-Filled Subarrays is a medium coding problem on arrays, math and counting, asked in Amazon, Google and Paytm interviews.
- 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
Hints for Number of Zero-Filled Subarrays
Hint 1
A run of
Lconsecutive zeros containsL * (L + 1) / 2all-zero subarrays.Hint 2
You can accumulate that total without ever computing
L: at each zero, add the current run length.Hint 3
A non-zero element resets the run to 0.
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 to0. - Add
runto 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) / 2only 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 totalJava
public static int zeroFilledSubarray(int[] nums) {
int total = 0, run = 0;
for (int x : nums) {
run = x == 0 ? run + 1 : 0;
total += run;
}
return total;
}C++
int zeroFilledSubarray(vector<int>& nums) {
int total = 0, run = 0;
for (int x : nums) {
run = x == 0 ? run + 1 : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays