We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Zero-Filled Subarrays

Difficulty: Medium

Problem Description

Given an integer array nums, return the number of subarrays filled with 0. A subarray is a contiguous non-empty sequence of elements within an array.

Key Insights

  • A subarray filled with 0 can have varying lengths, and each length contributes to the total count of subarrays.
  • For a contiguous segment of k zeros, the number of subarrays can be computed using the formula: k * (k + 1) / 2.
  • We need to traverse the array to count the lengths of contiguous segments of zeros and apply the formula for each segment.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a simple linear traversal of the array. We maintain a count of consecutive zeros. When we encounter a non-zero value or reach the end of the array, we calculate the number of zero-filled subarrays using the count of consecutive zeros collected so far. This approach leverages the mathematical formula for counting subarrays within contiguous segments.

Code Solutions

def zeroFilledSubarray(nums):
    count = 0  # Total count of zero-filled subarrays
    current_zeros = 0  # Count of consecutive zeros
    
    for num in nums:
        if num == 0:
            current_zeros += 1  # Increment count of consecutive zeros
        else:
            count += (current_zeros * (current_zeros + 1)) // 2  # Calculate subarrays for the segment
            current_zeros = 0  # Reset count for the next segment
    
    count += (current_zeros * (current_zeros + 1)) // 2  # Account for trailing zeros
    return count
← Back to All Questions