2348. Number of Zero-Filled Subarrays - Explanation

1. Brute Force

Intuition

The most straightforward approach is to check every possible subarray and count those filled entirely with zeros. For each starting index, we extend the subarray as long as we keep seeing zeros, incrementing our count for each valid zero-filled subarray we find.

Algorithm

Initialize a result counter res = 0.
For each starting index i from 0 to n-1:
- For each ending index j from i to n-1:
  - If nums[j] is not 0, break out of the inner loop.
  - Otherwise, increment res (we found another zero-filled subarray).
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if nums[j] != 0:
                    break
                res += 1
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Count Consecutive Zeros - I

Intuition

Instead of checking every subarray, we can be smarter by processing consecutive groups of zeros. When we find a sequence of k consecutive zeros, the number of zero-filled subarrays within that sequence is 1 + 2 + ... + k.

We can compute this incrementally: as we extend a run of zeros by one element, we add the current run length to our total. For example, if we have seen 3 zeros so far and see a 4th, we add 4 to the count (representing the 4 new subarrays ending at this position).

Algorithm

Initialize res = 0 and index i = 0.
While i < n:
- Initialize count = 0 for the current run of zeros.
- While nums[i] == 0:
  - Increment count.
  - Add count to res (this counts all subarrays ending at the current zero).
  - Increment i.
- Increment i to skip the non-zero element.
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = i = 0
        while i < len(nums):
            count = 0
            while i < len(nums) and nums[i] == 0:
                count += 1
                i += 1
                res += count
            i += 1
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Count Consecutive Zeros - II

Intuition

This is a cleaner version of the previous approach using a single loop. We maintain a running count of consecutive zeros. Each time we see a zero, we increment the count and add it to our result. Each time we see a non-zero, we reset the count to 0.

The key insight remains the same: when we are at the k-th consecutive zero, there are exactly k new zero-filled subarrays ending at this position (subarrays of length 1, 2, ..., k).

Algorithm

Initialize res = 0 and count = 0.
For each number in the array:
- If the number is 0, increment count.
- Otherwise, reset count = 0.
- Add count to res.
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = count = 0

        for num in nums:
            if num == 0:
                count += 1
            else:
                count = 0
            res += count

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

4. Count Consecutive Zeros (Math)

Intuition

Instead of adding incrementally during each run of zeros, we can use the mathematical formula directly. A sequence of k consecutive zeros contains exactly k * (k + 1) / 2 zero-filled subarrays (the sum of 1 + 2 + ... + k).

We scan through the array, counting the length of each consecutive zero sequence. When a sequence ends (we hit a non-zero or reach the end), we apply the formula to add all subarrays from that sequence at once.

Algorithm

Initialize res = 0 and count = 0.
For each number in the array:
- If the number is 0, increment count.
- Otherwise:
  - Add count * (count + 1) / 2 to res.
  - Reset count = 0.
After the loop, add the final count * (count + 1) / 2 to handle any trailing zeros.
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = count = 0
        for num in nums:
            if num == 0:
                count += 1
            else:
                res += (count * (count + 1)) // 2
                count = 0
        res += (count * (count + 1)) // 2
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Using Int Instead of Long for the Result

With an array of up to 10^5 elements, a long sequence of zeros (say, all zeros) would contribute n * (n + 1) / 2 subarrays, which can exceed 2^31 - 1. In Java and C++, using int for the result causes overflow. Always use long or long long for the result variable.

Forgetting to Handle Trailing Zeros in the Math Approach

When using the formula count * (count + 1) / 2 to count subarrays in each zero sequence, you must apply the formula one final time after the loop ends to handle any trailing zeros. A common bug is only applying the formula when hitting a non-zero element, missing the last zero sequence if the array ends with zeros.

Resetting Count at the Wrong Time

In the incremental approach, the count must be reset to 0 when encountering a non-zero element. A common mistake is resetting count before adding to the result, or forgetting to reset entirely, which causes zero sequences to be incorrectly merged across non-zero elements.