Number of Zero-Filled Subarrays

Leetcode Daily Challenge (21st March, 2023)

21 March, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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.

Link: https://leetcode.com/problems/number-of-zero-filled-subarrays/description/

Problem Explanation with 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.

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Intuition:-

To find the number of subarrays filled with 0s, first we need to find set of contiguous 0s with the count of each set.
For example, if the array is [1,0,0,0,1,0,0,1,0,0,0,0,0,1], then the set of contiguous 0s is [3,2,5].
Now for each set, we can find the number of subarrays filled with 0s by using the formula n*(n+1)/2.
For example, if the set is [3,2,5], then the number of subarrays filled with 0s is 3*(3+1)/2 + 2*(2+1)/2 + 5*(5+1)/2 = 21.
This formula you can figure out by drawing a few examples starting with n=1 to n=5.
Finally, we can return the sum of all the subarrays filled with 0s.
Instead of storing the count of each set we can directly find the number of subarrays there for that set and add it to the answer.

Solution:-

Initialize a variable c to 0 and a list zrs to store the set of contiguous 0s.
Iterate through the array and if the current element is not 0 and c is greater than 0, then we can append c to zrs and set c to 0.
If the current element is 0, then we can increment c by 1.
After the loop, if c is greater than 0, then we can append c to zrs to account for the last set of contiguous 0s.
Initialize a variable ans to 0.
Iterate through zrs and for each element, we can find the number of subarrays filled with 0s by using the formula n*(n+1)/2 and add it to ans.
Finally, we can return ans.

Code:-

JAVA Solution

class Solution {
    public int zeroFilledSubarray(int[] nums) {
        int c = 0;
        List<Integer> zrs = new ArrayList<Integer>();
        for (int i : nums) {
            if (i != 0 && c > 0) {
                zrs.add(c);
                c = 0;
            } else if (i == 0) {
                c += 1;
            }
        }
        if (c > 0) {
            zrs.add(c);
        }

        int ans = 0;
        for (int i : zrs) {
            ans += ((i*(i+1))/2);
        }
        return ans;
    }
}

Python Solution

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        c = 0
        zrs = []
        for i in nums:
            if i != 0 and c > 0:
                zrs.append(c)
                c = 0
            elif i == 0:
                c += 1
        if c > 0:
            zrs.append(c)

        ans = 0
        for i in zrs:
            ans += ((i*(i+1))//2)
        return ans

Complexity Analysis:-

TIME:-

Time complexity is O(n), where n is the length of the input array nums. This is because the code iterates over the input array once to identify the zero-filled subarrays, and then iterates over the resulting list of subarray lengths once to calculate the answer.

SPACE:-

Space complexity is O(k), where k is the number of zero-filled subarrays in the input array nums. This is because the code stores the length of each zero-filled subarray in a list zrs. The maximum size of this list is equal to the number of zero-filled subarrays in the input array.