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 tex_4562595408b95c8bbe0d988be302578e Teaching Kids Programming - Number of Zero-Filled Subarrays (GroupBy Algorithm + Math Counting) algorithms math python teaching kids programming youtube video , excluding one empty array, we have tex_543572fa43c168ab73a83f593078d411 Teaching Kids Programming - Number of Zero-Filled Subarrays (GroupBy Algorithm + Math Counting) algorithms math python teaching kids programming youtube video .

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) —

GD Star Rating
loading...
574 words
Last Post: Cloudflare Worker Unexpected High Usage of API Requests - How to Avoid Surprising Billing?
Next Post: A Simple Rate Limiter for CloudFlare Workers (Serverless API) based on KV Stores

The Permanent URL is: Teaching Kids Programming – Number of Zero-Filled Subarrays (GroupBy Algorithm + Math Counting)

Leave a Reply