Vultr DocsLatest Content

Number of Zero-Filled Subarrays

Updated on 14 July, 2025
Number of Zero-Filled Subarrays header image

Problem Statement

The task is to determine how many subarrays within a provided integer array nums are entirely comprised of zeros. A subarray is defined as a continuous part of the provided array that contains at least one element. For instance, consider an array containing elements [1, 3, 0, 0, 2, 0, 0, 4]. The goal is to look into all the possible subarrays and count how many of these are made up only of zero. This requires scanning through the array, spotting sequences of zeros, and calculating the number of possible subarrays that each sequence can generate.

Examples

Example 1

Input:

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

Output:

6

Explanation:

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

Explanation:

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

Explanation:

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

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Approach and Intuition

To solve this efficiently:

  1. Track Zero Streaks: Iterate through the array and count how many contiguous zeros appear in a row.
  2. Subarray Count Formula: For every streak of n consecutive zeros, the number of valid subarrays is n * (n + 1) / 2.
  3. Reset on Non-Zero: If a non-zero is encountered, reset the zero counter and add the previous streak’s subarrays to the total.
  4. End of Array Check: After the loop, account for any remaining zero streak at the end of the array.

This ensures linear time complexity, O(n), which is optimal given the input constraints.

Solutions

  • C++
cpp 
class Solution {
public:
    long long countZeroFilledSubarrays(vector<int>& elements) {
        long long total = 0, currentSubarrays = 0;
            
        for (int element : elements) {
            if (element == 0)
                currentSubarrays++;
            else
                currentSubarrays = 0;
            total += currentSubarrays;
        }
            
        return total;
    }
};

This solution is designed to solve the problem of counting zero-filled subarrays within a given array. The approach leveraged in the provided C++ code utilizes a linear pass through the array, using two counters to keep track of the cumulative number of zero-filled subarrays. Here's a concise explanation of the process:

  • Start by initializing two long long variables, total and currentSubarrays, to 0. total will store the count of all zero-filled subarrays found so far, while currentSubarrays keeps track of the number of zero-filled subarrays ending at the current position in the array.
  • Iterate through each element of the input array elements. For each element:
    • If the element is 0, increment currentSubarrays by 1. This is because a new subarray containing only zeros can be formed ending at this element.
    • If the element is not 0, reset currentSubarrays to 0 because any sequence of zeros is interrupted.
    • Add the value of currentSubarrays to total after each iteration, which accumulates the count of zero-filled subarrays that include the current element.
  • Finally, return the total, which represents the number of zero-filled subarrays in the entire array.

This solution is efficient with a time complexity of O(n), where n is the number of elements in the array, since it processes each element exactly once.

  • Java
java 
class Solution {
    public long countZeroFilledSubarrays(int[] values) {
        long total = 0, currentCount = 0;
            
        for (int val : values) {
            if (val == 0)
                currentCount++;
            else
                currentCount = 0;
            total += currentCount;
        }
            
        return total;
    }
}

The problem "Number of Zero-Filled Subarrays" is efficiently solved using Java. The given solution focuses on iterating through an array while counting continuous subarrays filled exclusively with zeroes.

Here's the step-by-step breakdown of the solution:

  1. Initialize total to zero. This variable stores the total count of zero-filled subarrays.
  2. Initialize currentCount to zero. This keeps track of the current length of consecutive zeros encountered.
  3. Loop through each value in the input array values:
    • If the value is zero, increment the currentCount as you have found one more zero to extend the current subarray.
    • If the value is not zero, reset currentCount to zero since the consecutive zeroes have ended.
    • Add the currentCount to total after each iteration. This step counts all possible zero-subarrays that end at the current index.

The final output (total) represents the total number of continuous zero subarrays found in the input array. This solution operates in linear time complexity O(n), where n is the number of elements in the array, as it only requires a single scan through the input array.

Comments

No comments yet.