Problem Statement
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.
Constraints:
1 ≤ nums.length ≤ 10^5
-10^9 ≤ nums[i] ≤ 10^9
Since the maximum size is 10^5
, your algorithm should ideally run in about O(n)
or O(n log n)
time to the efficient because something like O(n^2)
will give TLE.
LeetCode:
2348. Number of Zero-Filled Subarrays
Examples
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 are 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, 1999]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.
Different Approaches
Brute Force Approach (TLE)
Intuition:
Generate all subarrays and check if they are filled with 0
.
Code:
#include <bits/stdc++.h>
using namespace std;
long long zeroFilledSubarray(vector<int>& nums) {
long long count = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
bool allZero = true;
for (int k = i; k <= j; k++) {
if (nums[k] != 0) {
allZero = false;
break;
}
}
if (allZero) count++;
}
}
return count;
}
Complexity Analysis:
- Time Complexity:
O(n^3)
- Space Complexity:
O(1)
2️⃣ Better Brute Force Approach
- Avoid re-checking the inner loop.
- As we expand a subarray, if the current element is
0
, we extend the zero subarray count; otherwise, reset.
Code:
#include <bits/stdc++.h>
using namespace std;
long long zeroFilledSubarray(vector<int>& nums) {
long long count = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
long long zeros = 0;
for (int j = i; j < n; j++) {
if (nums[j] == 0) {
zeros++;
count++;
} else {
break; // stop, as subarray no longer all zeros
}
}
}
return count;
}
Complexity Analysis:
- Time Complexity:
O(n^2)
- Space Complexity:
O(1)
3️⃣ Optimal Approach (Mathematical / Counting)
Intuition:
- Traverse the array once.
- Keep track of current streak of zeroes.
- For each element:
- If it's
0
, extend streak -> add streak length to result. - If it's nonzero, reset streak.
- If it's
Code:
#include <bits/stdc++.h>
using namespace std;
long long zeroFilledSubarray(vector<int>& nums) {
long long count = 0, streak = 0;
for (int num : nums) {
if (num == 0) {
streak++;
count += streak; // add new subarrays ending here
} else {
streak = 0;
}
}
return count;
}
Complexity Analysis:
- Time Complexity:
O(n)
- Space Complexity:
O(1)