# Number of Zero-Filled Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-zero-filled-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/number-of-zero-filled-subarrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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 <= 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force with Nested Loops
This approach involves iterating through all possible subarrays, checking if each one is filled with zeros, and counting them. We can use two nested loops. The outer loop fixes the starting point of a subarray, and the inner loop extends the subarray to the right, counting valid zero-filled subarrays as it goes.
**Time:** O(n^2), where `n` is the length of the `nums` array. In the worst-case scenario, such as an array filled entirely with zeros, the inner loop runs `n-i` times for each `i`. This results in a total number of operations proportional to `n + (n-1) + ... + 1`, which is `n * (n+1) / 2`, leading to a quadratic time complexity. · **Space:** O(1), as we only use a constant amount of extra space for loop indices and the counter.
**Pros:** Simple to understand and implement.; Directly follows the definition of a subarray.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints (`n <= 10^5`).
### Explanation
The brute-force method systematically checks every possible contiguous subarray within the input array `nums`. We can implement this using two nested loops. The outer loop, with index `i`, selects the starting element of the subarray. The inner loop, with index `j`, extends the subarray from `i` to `j`.

For each starting position `i`, we iterate from `j = i` onwards. If `nums[j]` is `0`, we have found a valid zero-filled subarray `nums[i...j]`, so we increment our total count. If we encounter a non-zero element at `nums[j]`, we know that no subarray starting at `i` and ending at or after `j` can be zero-filled. This allows us to break the inner loop and move to the next starting position `i+1`, providing a slight optimization over a naive three-loop approach.

```java
class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // Start a new potential subarray at index i
            for (int j = i; j < n; j++) {
                // Extend the subarray to index j
                if (nums[j] == 0) {
                    // If nums[j] is 0, the subarray nums[i...j] is valid
                    count++;
                } else {
                    // If we find a non-zero, no more valid subarrays can start at i
                    break;
                }
            }
        }
        return count;
    }
}
```
While straightforward, this approach is computationally expensive as it re-evaluates parts of the array multiple times.
### Algorithm
1. Initialize a `long` variable `count` to `0` to store the total number of zero-filled subarrays.
2. Use a nested loop structure. The outer loop iterates from `i = 0` to `n-1`, where `n` is the length of the array. The index `i` represents the starting point of a subarray.
3. The inner loop iterates from `j = i` to `n-1`. The index `j` represents the ending point of the subarray.
4. For each subarray defined by `[i, j]`, check if the element `nums[j]` is `0`.
5. If `nums[j]` is `0`, it means the subarray from `i` to `j` consists only of zeros (because all previous elements from `i` to `j-1` must also have been zero for the inner loop to continue this far). Increment the `count`.
6. If `nums[j]` is not `0`, it means the current subarray and any subsequent subarrays starting at `i` cannot be zero-filled. Therefore, `break` the inner loop and proceed to the next starting index `i+1`.
7. After both loops complete, return the final `count`.

## Single Pass / Sliding Window
A much more efficient approach is to iterate through the array just once. We can count the number of zero-filled subarrays by keeping track of the length of the current contiguous sequence of zeros. The key insight is that a new zero at index `i` which extends a sequence of `k-1` zeros to a sequence of `k` zeros, adds `k` new subarrays (all subarrays ending at `i`).
**Time:** O(n), where `n` is the length of the `nums` array. This is because we perform a single pass through the array. · **Space:** O(1), as we only use a constant number of variables to store the counts, regardless of the input size.
**Pros:** Extremely efficient with a linear time complexity, making it suitable for large inputs.; Optimal solution as it processes each element only once.; Requires minimal extra space.; The implementation is concise and elegant.
**Cons:** The logic, while simple, might be slightly less intuitive at first glance compared to the brute-force approach. It relies on the insight that the number of new subarrays ending at the current position is equal to the length of the current zero sequence.
### Explanation
This optimal method avoids nested loops by processing the array in a single pass. The core idea is to count the length of the current contiguous sequence of zeros and accumulate the subarray counts on the fly.

We maintain a variable, `consecutiveZeros`, to track the length of the current streak of zeros. We iterate through the array. When we encounter a `0`, we increment `consecutiveZeros`. This new zero creates `consecutiveZeros` new subarrays that end at the current position. For example, if we see a third consecutive zero, it creates the subarrays `[0,0,0]`, `[0,0]`, and `[0]` that end at its position. So, we add the current `consecutiveZeros` count to our `totalCount`.

When we encounter a non-zero number, the streak is broken, so we reset `consecutiveZeros` to `0`. We still add `consecutiveZeros` (which is now 0) to the total, which has no effect.

This way, for any contiguous block of `k` zeros, we end up adding `1 + 2 + ... + k` to the total count, which correctly calculates the number of subarrays `k * (k + 1) / 2` for that block. The total count variable must be a `long` to prevent overflow, as the result can be large.

```java
class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long totalCount = 0;
        long consecutiveZeros = 0;
        
        for (int num : nums) {
            if (num == 0) {
                // We found a zero, extend the current sequence
                consecutiveZeros++;
            } else {
                // The sequence of zeros is broken
                consecutiveZeros = 0;
            }
            // Add the number of new subarrays ending at the current position
            totalCount += consecutiveZeros;
        }
        
        return totalCount;
    }
}
```
### Algorithm
1. Initialize two `long` variables: `totalCount = 0` to store the final result and `consecutiveZeros = 0` to track the length of the current contiguous block of zeros.
2. Iterate through each number `num` in the input array `nums`.
3. If `num` is `0`, increment `consecutiveZeros`.
4. If `num` is not `0`, it means the block of zeros has ended, so reset `consecutiveZeros` to `0`.
5. In each step of the iteration (regardless of whether the number is zero or not), add the current value of `consecutiveZeros` to `totalCount`.
6. After iterating through the entire array, return `totalCount`.

# Solutions
### Java

```java
class Solution {
public
  long zeroFilledSubarray(int[] nums) {
    long ans = 0;
    int cnt = 0;
    for (int v : nums) {
      cnt = v != 0 ? 0 : cnt + 1;
      ans += cnt;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long zeroFilledSubarray(vector<int> &nums) {
    long long ans = 0;
    int cnt = 0;
    for (int &v : nums) {
      cnt = v ? 0 : cnt + 1;
      ans += cnt;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int: ans = cnt = 0 for v in nums: cnt = 0 if v else cnt + 1 ans += cnt return ans

```