Number of Zero-Filled Subarrays

How it works

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.

Steps

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

Complexity

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

Things to watch for

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.

from typing import List

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

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long res = 0, count = 0;
        for (int num : nums) {
            if (num == 0) {
                count++;
            } else {
                res += count * (count + 1) / 2;
                count = 0;
            }
        }
        res += count * (count + 1) / 2;
        return res;
    }
};