#2348

Medium

LeetCode Problem Workspace

Number of Zero-Filled Subarrays

Given an array of integers, count the subarrays that consist entirely of 0s.

Problem Statement

You are given an integer array nums. Your task is to return the number of subarrays that consist entirely of zeros.

A subarray is a contiguous non-empty sequence of elements within the array. For example, in the array [1, 0, 0, 2], subarrays consisting of only zeros would be [0] and [0, 0].

Examples

Example 1

Input: nums = [1,3,0,0,2,0,0,4]

Output: 6

There are 4 occurrences of [0] as a subarray. There are 2 occurrences of [0,0] as a subarray. There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.

Example 2

Input: nums = [0,0,0,2,0,0]

Output: 9

There are 5 occurrences of [0] as a subarray. There are 3 occurrences of [0,0] as a subarray. There is 1 occurrence of [0,0,0] as a subarray. There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.

Example 3

Input: nums = [2,10,2019]

Output: 0

There is no subarray filled with 0. Therefore, we return 0.

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109

Solution Approach

Identifying Consecutive Zeros

By iterating through the array, track the length of consecutive zeros. For each zero encountered, add to the count of subarrays that end at that index based on the number of zeros so far. This ensures that every zero contributes to the count in an efficient manner.

Cumulative Count of Zero-Filled Subarrays

Each time a zero is found, you can increment a counter to track the number of zero-filled subarrays ending at that zero. This turns the problem from brute force into a simple linear scan of the array, summing the contributions of each zero segment.

Space Optimization

To optimize space complexity, you do not need to store all zero subarrays. Instead, use a running count and adjust as you iterate through the array. This reduces the problem to O(n) time and O(1) space complexity.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) because we process each element in the array once. The space complexity is O(1) since we only need a few counters, regardless of the input size.

What Interviewers Usually Probe

The candidate recognizes the need to count consecutive zeros efficiently.
The candidate can optimize space usage while keeping the time complexity linear.
The candidate avoids brute force and handles large input sizes effectively.

Common Pitfalls or Variants

Common pitfalls

Forgetting to reset the consecutive zero count after encountering a non-zero element.
Underestimating the total number of subarrays when multiple consecutive zeros appear.
Using nested loops to check for zero subarrays, leading to inefficient solutions.

Follow-up variants

Modify the problem to count subarrays filled with ones instead of zeros.
Consider a similar problem but with non-zero elements where you count subarrays with sums equal to a target value.
Extend the problem to multidimensional arrays, counting subarrays in a 2D matrix.

FAQ

What is the main pattern for solving the 'Number of Zero-Filled Subarrays' problem?

The main pattern involves recognizing that each zero contributes to multiple subarrays, with consecutive zeros forming increasing numbers of subarrays as you progress through the array.

How do I calculate the number of zero-filled subarrays?

For each zero, track the number of consecutive zeros up to that point. The number of zero-filled subarrays ending at that position is equal to the number of consecutive zeros seen so far.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array. This is because the solution involves a single pass through the array.

Can this problem be solved without extra space?

Yes, by keeping a running count of the consecutive zeros, the problem can be solved with O(1) extra space.

What are some common mistakes when solving this problem?

A common mistake is not resetting the consecutive zero count after encountering a non-zero element, or using a brute force method that leads to inefficient solutions.

terminal

Solution

Solution 1: Traversal and Counting

We traverse the array $\textit{nums}$ and use a variable $\textit{cnt}$ to record the current number of consecutive $0$s. For the current element $x$ we are traversing, if $x$ is $0$, then $\textit{cnt}$ is incremented by $1$, and the number of all-zero subarrays ending with the current $x$ is $\textit{cnt}$, which we add to the answer. Otherwise, we set $\textit{cnt}$ to $0$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = cnt = 0
        for x in nums:
            if x == 0:
                cnt += 1
                ans += cnt
            else:
                cnt = 0
        return ans

Continue Practicing

#2344 minimum deletions to make array divisible #2358 maximum number of groups entering a competition #2364 count number of bad pairs