Number Of Zero Filled Subarrays - Leetcode Solution

Problem Statement:

Given an array of integers nums, return the number of non-empty subarrays that have at least one zero in them.

Example: Input: nums = [0,1,0,0,5,6] Output: 6

Solution:

We can solve this problem by using an efficient algorithm called "Sliding Window". This algorithm works on the principle of maintaining a window of elements in the array and then moving the window by one index at a time to search for the desired subarrays.

Step 1: Initialize two pointers "left" and "right" to point to the first element in the array. Step 2: Initialize a variable "count" to 0 to keep track of the number of subarrays with at least one zero. Step 3: Loop through the array until the "right" pointer reaches the end of the array. Step 4: If the current element pointed by the "right" pointer is zero, then increment the "count" variable by 1. Step 5: If the current element pointed by the "right" pointer is not zero, then move the "left" pointer to the next index. Step 6: If the "left" pointer is equal to the "right" pointer, then move both pointers to the next index. Step 7: Repeat steps 4 to 6 until the end of the array is reached. Step 8: Return the "count" variable.

Here's the code for the solution:

class Solution { public: int countSubArrays(vector<int>& nums) { int left = 0, right = 0, count = 0; while (right < nums.size()) { if (nums[right] == 0) { count++; } while (count > 0) { if (nums[left] == 0) { count--; } left++; } right++; } return ((nums.size() * (nums.size() + 1)) / 2) - ((left * (left + 1)) / 2); } };

Explanation:

In the above code, we first initialize the "left" and "right" pointers to the first element in the array and the "count" variable to 0. We then loop through the array until the "right" pointer reaches the end of the array. If the current element pointed by the "right" pointer is zero, then we increment the "count" variable. If the current element pointed by the "right" pointer is not zero, then we move the "left" pointer to the next index. We then check if the "left" pointer is equal to the "right" pointer. If it is, then we move both pointers to the next index. We continue this process until the end of the array is reached.

Finally, we return the total number of possible subarrays (nums.size()* (nums.size()+1))/2 and subtract the number of subarrays that don't contain any zeroes (left*(left+1))/2. This gives us the total number of subarrays that have at least one zero in them.

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the size of the input array. This is because we are traversing the input array only once and performing constant time operations at each element.

Space Complexity:

The space complexity of the above algorithm is O(1), as we are not using any extra space apart from the input array.

1