Problem of The Day: Number of Zero-Filled Subarrays

Problem Statement

leetcode problem link

Brute Force approach [Accepted]

class Solution:
    def calculate(self, i, j):
        n = j - i + 1
        ans = 0
        for k in range(n):
            ans += k
        return ans

    def zeroFilledSubarray(self, nums: List[int]) -> int:
        if 0 not in nums:
            return 0

        N = len(nums)
        res = 0
        seen = set()
        for i in range(N):
            if nums[i] == 0 and i not in seen:
                seen.add(i)
                j = i + 1
                while j < N and nums[j] == 0:
                    seen.add(j)
                    j += 1
                res += self.calculate(i, j)

        return res

Editorial

Approach: Count the number of consecutive 0’s.

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

        # Iterate over nums, if num = 0, it has 1 more zero-filled subarray
        # than the previous one, otherwise, it has 0 zero-filled subarray.
        for num in nums:
            if num == 0:
                num_subarray += 1
            else:
                num_subarray = 0
            ans += num_subarray

        return ans