2348. Number of Zero-Filled Subarrays

Problem Description

The problem requires us to find the total number of subarrays in a given integer array where every element is 0. A subarray is defined as a contiguous sequence of elements within the array. This means that we are looking for all the continuous sequences of zeroes in the array and want to count them. It is important to realize that this includes subarrays of different lengths, starting and ending at any indices where zeros are contiguous.

Intuition

The intuition behind the solution approach is fairly straightforward. We want to iterate through the array and keep track of contiguous sequences of zeros. To achieve this, we can maintain a count (cnt) that keeps track of the length of the current sequence of zeros we are in.

Starting from the beginning of the array, for each element, we check whether it is a zero:

If it is, we increment our current zero sequence length count (cnt) by 1, since we've found an additional zero in our current subarray of zeros.
If it isn't, we reset our count to 0 as we're no longer in a sequence of zeros.

Now, the key insight is that each new zero we encounter not only forms a subarray of length 1 by itself but also extends the length of all subarrays ending at the previous zero by 1. Therefore, at each step, we can add the current count of zeros to our answer (ans).

For each new zero found, we do not need to recount all the subarrays it could create with all preceding zeros. We just realize that it extends them all by one. Thus, the current running cnt can be added directly to ans to account for all new subarrays ending at this zero.

This way, we effectively count all zero-filled subarrays without having to explicitly enumerate them all, leading to an efficient solution.

Learn more about Math patterns.

Solution Approach

The implemented solution relies on a simple linear scan of the input array, which implicitly tracks the size of contiguous zero-filled subarrays. Two main variables are introduced: ans and cnt. No additional data structures are needed, highlighting the simplicity and efficiency of the approach.

Let's delve deeper into the steps:

Initialize ans and cnt to 0. ans will keep the running total of all zero-filled subarray counts, while cnt will track the current number of zeros in a contiguous sequence.
Iterate through each value v in the nums array:

a. If v is not 0, reset cnt to 0. This step is important as it signifies that the current sequence of zeros has ended and any new sequence found later will be independent of any zeros previously encountered.

b. If v is 0, increment cnt by 1, since we've found an additional zero that extends the current zero-filled subarray.
After each iteration, add the value of cnt to ans. This is because every new zero found (or every zero in a contiguous sequence of zeros) not only represents a subarray of one element (itself) but also extends the length of any zero-filled subarray ending at the previous zero by one. Therefore, cnt also represents the number of new zero-filled subarrays that the current 0 contributes to.
Continue this process until the end of the array.
Once the iteration is complete, ans will contain the total number of zero-filled subarrays in the array.

The time complexity of this approach is O(n), where n is the number of elements in the array, since it requires a single pass through the array. The space complexity is O(1), as the solution uses a constant amount of extra space.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's use a small example with the array nums = [1, 0, 0, 2, 0].

Initialize ans and cnt to 0. There are no zero-filled subarrays counted yet, and no current sequence of zeros.
Start iterating through the nums array:
- At the first element 1, cnt remains 0 as it is not a zero.
- At the second element 0, increment cnt to 1. This zero forms a new subarray [0]. Add cnt to ans, so ans becomes 1.
- At the third element 0, increment cnt to 2. This zero extends the previous subarray to form a new one [0, 0] and also makes an individual subarray [0]. Add cnt to ans, so ans becomes 1 + 2 = 3.
- At the fourth element 2, reset cnt to 0 as the sequence of zeros has been broken.
- At the fifth element 0, increment cnt to 1. This zero forms a new subarray [0]. Add cnt to ans, so ans becomes 3 + 1 = 4.
By the end of the array, we've counted all zero-filled subarrays: [0], [0, 0], and two separate [0] subarrays after the 2. Therefore, the total number of zero-filled subarrays in this example is 4.

Thus, ans holds the correct total, and the process demonstrates both the resetting of cnt when non-zero elements are encountered and the accumulation of the number of subarrays in ans as zero elements are processed. The approach ensures we count consecutive sequences of zeros efficiently without unnecessary enumeration.

Solution Implementation

1from typing import List
2
3class Solution:
4    def zero_filled_subarray(self, nums: List[int]) -> int:
5        # Initialize the counter for current zero sequence and the answer accumulator
6        current_zero_count = total_subarrays = 0
7      
8        # Iterate over each number in the input list
9        for num in nums:
10            if num == 0:
11                # If the current number is zero, increment the current zero sequence counter
12                current_zero_count += 1
13            else:
14                # If the current number is not zero, reset the counter
15                current_zero_count = 0
16          
17            # Add the current zero sequence length to the total number of subarrays
18            # This works because for each new zero, there are `current_zero_count` new subarrays ending with that zero
19            total_subarrays += current_zero_count
20      
21        # Return the total count of zero-filled subarrays
22        return total_subarrays
23

1class Solution {
2    // Method to calculate the number of zero-filled contiguous subarrays
3    public long zeroFilledSubarray(int[] nums) {
4        long totalCount = 0;  // Initialize total count of zero-filled subarrays
5        int zeroCount = 0;   // Initialize count of consecutive zeros
6
7        // Iterate through the array elements
8        for (int value : nums) {
9            // Reset zeroCount to 0 if the current element is not zero
10            // Otherwise, increment zeroCount
11            zeroCount = (value != 0) ? 0 : zeroCount + 1;
12            // Add the current zeroCount to the total count
13            totalCount += zeroCount;
14        }
15
16        return totalCount;  // Return the total count of zero-filled subarrays
17    }
18}
19

1class Solution {
2public:
3    // Function to calculate the number of zero-filled subarrays.
4    long long zeroFilledSubarray(vector<int>& nums) {
5        long long answer = 0; // Variable to store the final answer.
6        int zeroCount = 0; // Counter to keep track of consecutive zeros.
7
8        // Iterate through the numbers in the vector.
9        for (int value : nums) {
10            // Reset the counter if the current value is not zero, otherwise increase it.
11            zeroCount = (value != 0) ? 0 : zeroCount + 1;
12          
13            // Add the number of new zero-filled subarrays ending with the current value.
14            answer += zeroCount;
15        }
16      
17        // Return the total number of zero-filled subarrays found.
18        return answer;
19    }
20};
21

1function zeroFilledSubarray(nums: number[]): number {
2    let totalSubarrays = 0; // This variable will hold the total count of zero-filled subarrays
3    let currentZerosCount = 0; // This variable tracks the current consecutive zeros count
4
5    // Loop through each number in the nums array
6    for (const value of nums) {
7        if (value === 0) {
8            // If the current value is zero, increment the current consecutive zeros count
9            currentZerosCount++;
10        } else {
11            // If it's not zero, reset the count to 0
12            currentZerosCount = 0;
13        }
14        // Add the currentZerosCount to the total subarrays count which also includes
15        // all subarrays ending with the current element
16        totalSubarrays += currentZerosCount;
17    }
18
19    // Return the total number of zero-filled subarrays found in the nums array
20    return totalSubarrays;
21}
22

Time and Space Complexity

The provided code snippet has a time complexity of O(n), where n is the length of the input list nums. This is because the code iterates through the list once, performing a constant number of operations for each element.

The space complexity of this code is O(1). No additional space proportional to the input size is used; the variables ans and cnt use a fixed amount of space regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: