Number of Zero-Filled Subarrays
Leetcode Daily Challenge (21st March, 2023)
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 <= 10<sup>5</sup>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
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
cto 0 and a listzrsto 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
ctozrsand setcto 0.If the current element is 0, then we can increment
cby 1.After the loop, if
cis greater than 0, then we can appendctozrsto account for the last set of contiguous 0s.Initialize a variable
ansto 0.Iterate through
zrsand for each element, we can find the number of subarrays filled with 0s by using the formulan*(n+1)/2and add it toans.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.