Number of Zero-Filled Subarrays solution and explanation
Google
9 more videos on this problem
Number of Zero-Filled Subarrays - Leetcode 2348 - PythonNeetCodeIO · 10:55 · 16K views
Number of Zero-Filled Subarrays | 2 Approaches | Leetcode 2348 | Meta | codestorywithMIKcodestorywithMIK · 16:40 · 7K views
Number of Zero-Filled Subarrays || 2 Pointer & 3 other ApproachesAryan Mittal · 15:01 · 2K views
2348. Number of Zero-Filled Subarrays - JAVA (Math - Detailed explanation)Sourin Majumdar · 8:10 · 987 views
Number of Zero-Filled Subarrays - Leetcode 2348 - PythonTechError · 5:16 · 821 views
2348. Number of Zero-Filled Subarrays (Leetcode Medium)Programming Live with Larry · 5:12 · 520 views
Number of Zero Filled Subarrays | LeetCode 2348 | Array | Math | Google Interview Question | EasyCode Harmony · 21:56 · 388 views
2348. Number of Zero-Filled Subarrays | Leetcode Daily - PythonLeetcode Daily · 4:32 · 360 views
LeetCode 2348 Number of Zero-Filled Subarrays - Biweekly Contest 83 - Java SolutionJeff Academy · 4:11 · 329 views
Number of Zero Filled Subarrays - LeetCode 2348 - Java Solutionalgobest - Computer Science · 2:08 · 147 views
The problem
Given an integer array nums, return the number of subarrays filled with 0.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,3,0,0,2,0,0,4] Output: 6 Explanation: There are 4 occurrences of [0] as a subarray. There are 2 occurrences of [0,0] as a subarray. There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.
Example 2:
Input: nums = [0,0,0,2,0,0] Output: 9 Explanation: There are 5 occurrences of [0] as a subarray. There are 3 occurrences of [0,0] as a subarray. There is 1 occurrence of [0,0,0] as a subarray. There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.
Example 3:
Input: nums = [2,10,2019] Output: 0 Explanation: There is no subarray filled with 0. Therefore, we return 0.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109
Approach overview
Problem Overview: Given an integer array nums, count how many subarrays contain only zeros. A valid subarray must consist entirely of 0 values and can be any contiguous portion of the array.
The key observation: zero-filled subarrays only come from contiguous blocks of zeros. If a block contains k zeros, it contributes multiple subarrays of different lengths.
Approach 1: Contiguous Zero Segment Counting (O(n) time, O(1) space)
Scan the array and identify contiguous segments of zeros. Suppose a segment contains k zeros. The number of subarrays that can be formed from that segment equals k * (k + 1) / 2. This works because each position can start a subarray and extend through the remaining zeros. For example, a run of 3 zeros produces subarrays: [0], [0], [0], [0,0], [0,0], and [0,0,0]. Iterate through the array, track the length of each zero run, compute the formula when the run ends, and add it to the total. This approach relies only on sequential traversal of the array and a simple combinatorial formula from math. Time complexity is O(n) because each element is visited once, and space complexity is O(1).
Approach 2: Running Zero Count Accumulation (O(n) time, O(1) space)
Instead of computing the contribution of a whole segment at once, accumulate it incrementally. Maintain a variable zeroCount representing the current streak of consecutive zeros. While iterating through the array, if the current value is zero, increment zeroCount and add it directly to the result. If the value is non‑zero, reset zeroCount to zero. The intuition: when you extend a zero streak, every new zero creates additional subarrays ending at the current index. For example, the third zero in a streak contributes three new subarrays ending there. This approach still performs a single pass through the array, but avoids explicitly calculating segment lengths. Time complexity remains O(n) with O(1) auxiliary space.
Recommended for interviews: The running accumulation approach is usually preferred. It shows you recognize how subarrays grow dynamically and can compute the result during iteration. The contiguous segment method also works and clearly demonstrates the combinatorial insight (k * (k + 1) / 2). In interviews, explaining the segment formula first and then implementing the running count version often shows stronger problem‑solving depth.
Approach 1: Approach 1: Count zero subarrays using a contiguous segments approach
This approach involves iterating through the array and counting the length of contiguous segments of zeros. For each segment of zeros with length n, the total number of zero-filled subarrays is the sum of the first n natural numbers.
For a segment with length n, the number of zero-filled subarrays is (n * (n + 1)) / 2. This formula is derived from the well-known sum formula for the first n integers.
class Solution:
def zeroFilledSubarray(self, nums):
count = 0
subarray_count = 0
for num in nums:
if num == 0:
count += 1
else:
count = 0
subarray_count += count
return subarray_countpublic class Solution {
public long zeroFilledSubarray(int[] nums) {
int count = 0;
long subarrayCount = 0;
for (int num : nums) {
if (num == 0) {
count++;
} else {
count = 0;
}
subarrayCount += count;
}
return subarrayCount;
}
}#include <vector>
using namespace std;
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
int count = 0;
long long subarrayCount = 0;
for (int num : nums) {
if (num == 0) {
count++;
} else {
count = 0;
}
subarrayCount += count;
}
return subarrayCount;
}
};var zeroFilledSubarray = function(nums) {
let count = 0;
let subarrayCount = 0;
for (const num of nums) {
if (num === 0) {
count++;
} else {
count = 0;
}
subarrayCount += count;
}
return subarrayCount;
};#include <stdio.h>
int zeroFilledSubarray(int* nums, int numsSize) {
int count = 0;
long long subarrayCount = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0) {
count++;
} else {
count = 0;
}
subarrayCount += count;
}
return subarrayCount;
}public class Solution {
public long ZeroFilledSubarray(int[] nums) {
int count = 0;
long subarrayCount = 0;
foreach (int num in nums) {
if (num == 0) {
count++;
} else {
count = 0;
}
subarrayCount += count;
}
return subarrayCount;
}
}The Python solution leverages a simple loop to maintain a count of consecutive zeros, summing this count to the total number of subarrays each time the loop progresses.
Time Complexity: O(n), iterating through the array once.
Space Complexity: O(1), using only a few extra variables.
Approach 2: Approach 2: Accumulative count of zero subarrays
This approach is slightly variation. We keep track of the number of zero subarrays as we proceed through the array. Whenever a zero is encountered, the count of zero subarrays ending at that position is incremented by the number of zero subarrays ending at the previous position plus one. When a non-zero is encountered, we reset our counter.
class Solution:
def zeroFilledSubarray(self, nums):
count = 0
zero_ends_here = 0
for num in nums:
if num == 0:
zero_ends_here += 1
count += zero_ends_here
else:
zero_ends_here = 0
return countpublic class Solution {
public long zeroFilledSubarray(int[] nums) {
long count = 0, zeroEndsHere = 0;
for (int num : nums) {
if (num == 0) {
zeroEndsHere++;
count += zeroEndsHere;
} else {
zeroEndsHere = 0;
}
}
return count;
}
}#include <vector>
using namespace std;
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
long long count = 0, zeroEndsHere = 0;
for (int num : nums) {
if (num == 0) {
zeroEndsHere++;
count += zeroEndsHere;
} else {
zeroEndsHere = 0;
}
}
return count;
}
};var zeroFilledSubarray = function(nums) {
let count = 0;
let zeroEndsHere = 0;
for (const num of nums) {
if (num === 0) {
zeroEndsHere++;
count += zeroEndsHere;
} else {
zeroEndsHere = 0;
}
}
return count;
};#include <stdio.h>
int zeroFilledSubarray(int* nums, int numsSize) {
int count = 0;
int zeroEndsHere = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0) {
zeroEndsHere = zeroEndsHere + 1;
count += zeroEndsHere;
} else {
zeroEndsHere = 0;
}
}
return count;
}public class Solution {
public long ZeroFilledSubarray(int[] nums) {
long count = 0;
int zeroEndsHere = 0;
foreach (int num in nums) {
if (num == 0) {
zeroEndsHere++;
count += zeroEndsHere;
} else {
zeroEndsHere = 0;
}
}
return count;
}
}The Python implementation counts subarrays by adding to zero_ends_here with each zero found, contributing to count, and resets when needed.
Time Complexity: O(n) - one pass over the input list.
Space Complexity: O(1) - no extra space required beyond tracking counts.
Approach 3: Traversal and Counting
We traverse the array nums and use a variable cnt to record the current number of consecutive 0s. For the current element x we are traversing, if x is 0, then cnt is incremented by 1, and the number of all-zero subarrays ending with the current x is cnt, which we add to the answer. Otherwise, we set cnt to 0.
After the traversal, we return the answer.
Time complexity O(n), where n is the length of the array nums. Space complexity O(1).
Similar problems:
function zeroFilledSubarray(nums: number[]): number {
let [ans, cnt] = [0, 0];
for (const x of nums) {
if (!x) {
ans += ++cnt;
} else {
cnt = 0;
}
}
return ans;
}func zeroFilledSubarray(nums []int) (ans int64) {
cnt := 0
for _, x := range nums {
if x == 0 {
cnt++
ans += int64(cnt)
} else {
cnt = 0
}
}
return
}impl Solution {
pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
let mut ans: i64 = 0;
let mut cnt: i64 = 0;
for x in nums {
if x == 0 {
cnt += 1;
ans += cnt;
} else {
cnt = 0;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Count zero subarrays using a contiguous segments approach | Time Complexity: O(n), iterating through the array once. Space Complexity: O(1), using only a few extra variables. |
| Approach 2: Accumulative count of zero subarrays | Time Complexity: O(n) - one pass over the input list. Space Complexity: O(1) - no extra space required beyond tracking counts. |
| Traversal and Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Contiguous Zero Segment Counting | O(n) | O(1) | When you want a clear mathematical explanation using the k*(k+1)/2 formula for each zero block |
| Running Zero Count Accumulation | O(n) | O(1) | Best for interviews and clean implementations that compute results during a single pass |
Frequently asked questions
Is Number of Zero-Filled Subarrays easy or hard?
The problem is rated Medium on LeetCode but often feels easier once the contiguous zero insight is recognized. Beginners may attempt nested loops initially, but the optimal O(n) solution comes from understanding how zero streaks generate multiple subarrays.
Number of Zero-Filled Subarrays Python/Java solution
Both Python and Java implementations typically follow the running zero-count technique. Maintain a variable tracking consecutive zeros, add it to the result whenever another zero appears, and reset when a non-zero element occurs. The algorithm runs in O(n) time and uses constant extra space.
How to solve Number of Zero-Filled Subarrays in O(n)?
Traverse the array while maintaining a counter for consecutive zeros. If the current element is zero, increment the counter and add it to the total number of subarrays. If the element is non‑zero, reset the counter to zero. This works because each additional zero extends all existing zero subarrays ending at the current index.
What is the best approach for Number of Zero-Filled Subarrays?
The most practical approach uses a running count of consecutive zeros while scanning the array once. Each time a zero appears, increment the streak and add it to the result. This counts all subarrays ending at that position. The method runs in O(n) time with O(1) space and avoids explicitly computing segment lengths.
Is Number of Zero-Filled Subarrays asked at Google/Amazon/Meta?
This pattern appears in interviews at companies like Amazon and Google where candidates must count subarrays or analyze contiguous segments. Variations often involve counting subarrays with specific values or constraints. Recognizing streak-based counting is a common expectation.
What data structure is used in Number of Zero-Filled Subarrays?
The problem primarily uses array traversal and simple integer counters. No advanced data structures like heaps or hash maps are required. The logic relies on tracking contiguous zero streaks and applying a mathematical counting principle.
What is the time complexity of Number of Zero-Filled Subarrays?
The optimal solutions run in O(n) time because the array is traversed once. Each element contributes constant work—either incrementing a zero streak or resetting it. Space complexity is O(1) since only a few counters are maintained.