Teaching Kids Programming – Number of Zero-Filled Subarrays (GroupBy Algorithm + Math Counting)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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 <= 10^5
-10^9 <= nums[i] <= 10^9

Hints:
For each zero, you can calculate the number of zero-filled subarrays that end on that index, which is the number of consecutive zeros behind the current element + 1.
Maintain the number of consecutive zeros behind the current element, count the number of zero-filled subarrays that end on each index, sum it up to get the answer.

Number of Zero-Filled Subarrays (GroupBy Algorithm + Math Counting)

The total number of subarrays (if size is N) is , excluding one empty array, we have .

So, we just have to group the zeros subarray and accumulate the count. We can do this via itertools.groupby which returns an iterator to the unique key and iterator to the corresponding group (continuous same elements)

1
2
3
4
5
6
7
8

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        for g, l in itertools.groupby(nums):
            if g == 0:
                n = len(list(l))
                ans += n * (n + 1) // 2
        return ans

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        for g, l in itertools.groupby(nums):
            if g == 0:
                n = len(list(l))
                ans += n * (n + 1) // 2
        return ans

The time complexity is O(N). The space complexity is O(1) constant assuming itertools.groupby algorithms also O(1).

Another algorithm is to iterate over the elements, and keep tracking of the number of continuous zeros we are now), and then accumulate the contribution. See below implementation O(N) time and O(1) space.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        c = 0
        for i in nums:
            if i == 0:
                c += 1
                ans += c
            else:
                c = 0
        return ans

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        c = 0
        for i in nums:
            if i == 0:
                c += 1
                ans += c
            else:
                c = 0
        return ans

–EOF (The Ultimate Computing & Technology Blog) —