2348. Number of Zero-Filled Subarrays

Posted on In Words count: 1.8k Reading time ≈ 2 mins.

2348. Number of Zero-Filled Subarrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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

Difficulty : Medium

Solution

The solution uses a simple iterative approach to count the number of subarrays filled with 0. We maintain two variables ans and cur. ans stores the total count of subarrays filled with 0, and cur stores the count of subarrays ending at the current index that are filled with 0.

We iterate through the given array nums and check if the current element is 0 or not. If the current element is 0, we increment cur and add its value to ans. If the current element is not 0, we reset cur to 0.

The reason we add cur to ans is that for every 0 in the array, there are cur subarrays that end at that index and are filled with 0. For example, if we have the input [1,3,0,0,2,0,0,4], the first 0 will be part of one subarray filled with 0, and the second 0 will be part of two subarrays filled with 0. Hence, we add the value of cur to ans.

Time Complexity

O(N)

Space Complexity

O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long ans = 0;
        long cur = 0;
        for (int num : nums) {
            if (num == 0) {
                cur++;
                ans += cur;
            } else {
                cur = 0;
            }
        }
        return ans;
    }
}