Arrays - Number of Zero Filled Subarrays

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.

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.
So, there are total of 6 subarrays with only 0's in it.

Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.

Constraints:

1 <= nums.length <= 10⁵
-109 <= nums[i] <= 109

Solution 1 - Compute the 0's count and add them to result as cumulative sum

Let's understand this approach with an example:

If there is only one zero in the sub array [0], then the result will be 1.
If there are two zero's in the sub array [0, 0], then the result will be 3, there are two subarrays with one zero in it, and another subarray with two zeros.
If there are three zero's in the sub array [0, 0, 0], then the result will be 6, there are three subarrays with one zero in it, , two subarrays with two zeros, and one subarray with three zeros.
If there are four zero's in the sub array [0, 0, 0, 0], then the result will be 10, there are four subarrays with one zero in it, , three subarrays with two zeros, two subarrays with three zeros, and one subarray with four zeros.
If there are four zero's in the sub array [0, 0, 0, 0, 0], then the result will be 15, there are five subarrays with one zero in it, , four subarrays with two zeros, three subarrays with three zeros, two subarrays with four zeros, and one subarray with five zeros.

If you notice a pattern in above examples, when you have a contiguous subarrays with zero's in it, each time you add a zero, we can simply add number zero's have found so far to total result. Let's look at the pattern in above example.

When one zero is there [0]--> result = 1.
When two zero's are there [0, 0]--> result = 1 (previous result) + 2 (Number of zeros) = 3 .
When two zero's are there [0, 0, 0]--> result = 3 (previous result) + 3 (Number of zeros) = 6 .
When two zero's are there [0, 0, 0, 0]--> result = 6 (previous result) + 4 (Number of zeros) = 10 .

Implementation steps:

We will first initialize two variables result and count.
Then, loop through elements of input array:
- If the element at index i is 0, then increment count, otherwise reset the count to 0.
- And keep adding the current count to the result.
Finally, return the result.

public class NumberOfZeroFilledSubArrays { static long zeroFilledSubarray(int[] nums) { long result = 0; long count = 0; for(int i=0; i<nums.length; i++) { if(nums[i] ==0) { count++; } else { count =0; } result = result + count; } return result; } public static void main(String[] args) { System.out.println(zeroFilledSubarray(new int[]{1,3,0,0,2,0,0,4})); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(1)

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: