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.
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 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.
Solution
Method 1 - Count subarrays on finding 0
Here is the approach:
- Traverse through the array to count contiguous sequences of zeros.
- For each sequence of zeros of length
n
, the number of subarrays is given by the sum of the firstn
natural numbers: ( \text{count} = \frac{n \times (n + 1)}{2} ).
Code
Java
public class Solution {
public int countZeroFilledSubarrays(int[] nums) {
int count = 0;
int zeroLength = 0;
for (int num : nums) {
if (num == 0) {
zeroLength++;
count += zeroLength;
} else {
zeroLength = 0;
}
}
return count;
}
}
Python
class Solution:
def countZeroFilledSubarrays(self, nums: List[int]):
count = 0
zero_length = 0
for num in nums:
if num == 0:
zero_length += 1
count += zero_length
else:
zero_length = 0
return count
Complexity
- ⏰ Time complexity:
O(n)
, wheren
is the length of the array, as we have to traverse the array once. - 🧺 Space complexity:
O(1)
, as we use a constant amount of extra space.