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:

1
2
3
4
5
6

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:

1
2
3
4
5
6
7

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:

1
2
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:

  1. Traverse through the array to count contiguous sequences of zeros.
  2. For each sequence of zeros of length n, the number of subarrays is given by the sum of the first n natural numbers: ( \text{count} = \frac{n \times (n + 1)}{2} ).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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), where n 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.