Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every zero-filled subarray lies entirely inside one maximal run of zeros. A run of length r contributes r*(r + 1)/2 subarrays, one for every choice of its start and end positions. Nonzero values separate independent runs.

Approach

Scan the array while counting consecutive zeros. When a nonzero value ends a run, add its triangular count and reset the counter. After the loop, add the final run's contribution if the array ended in zero. Return the accumulated count. Flushing that last run is essential because it has no following nonzero value to trigger the usual update.

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

        for x in nums:
            if x == 0:
                count += 1
            elif count != 0:
                res += comb(count + 1, 2)
                count = 0

        if count != 0:
            res += comb(count + 1, 2)

        return res

Complexity analysis

Let n = nums.length. Time: O(n) to scan maximal zero runs. Auxiliary space: O(1).