LeetCode Solutions Blog

Number of Zero-Filled Subarrays

Number: 2432

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array, count the number of contiguous subarrays that are entirely filled with 0.

Key Insights

A subarray is contiguous. For every sequence of consecutive 0's of length L, there are L * (L + 1) / 2 subarrays.
Iterating through the array and counting consecutive zeros is an efficient approach.
Once a non-zero element is encountered, compute the contributions from the current streak and then reset the count.
Handle the edge case where the array ends with a sequence of zeros.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1), as only a few counter variables are used.

Solution

We use a simple linear scan with an integer counter to track consecutive zeros. Every time we see a zero, we increase the count. When a non-zero is encountered (or at the end of the array), we calculate the number of subarrays for that block using the formula L * (L + 1) / 2 and add it to our total. This way, we ensure all zero-filled subarrays are considered efficiently.

Code Solutions

# Python solution for counting zero-filled subarrays.
def zeroFilledSubarray(nums):
    total_subarrays = 0  # To hold the total count of zero-filled subarrays.
    consecutive_zeros = 0  # To count the current consecutive zeros.
    
    # Iterate through each number in the array.
    for num in nums:
        if num == 0:
            consecutive_zeros += 1  # Increase count if the current element is 0.
        else:
            # When the streak of zeros ends, add the number of subarrays from the streak.
            total_subarrays += consecutive_zeros * (consecutive_zeros + 1) // 2
            consecutive_zeros = 0  # Reset the counter.
    
    # If the array ends with a streak of zeros, count them as well.
    total_subarrays += consecutive_zeros * (consecutive_zeros + 1) // 2
    return total_subarrays

# Example usage:
print(zeroFilledSubarray([1,3,0,0,2,0,0,4]))  # Output should be 6