Leetcode.com problem 2348: "Number of Zero-Filled Subarrays"

Leetcode.com problem 2348: Number of Zero-Filled Subarrays

James S. Plank

Tue Aug 19 18:19:29 EDT 2025

Problem Statement.
Success Rate (as of August, 2025): 70.1%
This is a "medium" problem.
Skeleton.cpp A skeleton with my main() that you can use to test your answer.
tests.sh: A testing script
answers.txt: Correct output to the testing script. MD5 Hash: f629452aa9cfb5816994b7989da30565.

In case Leetcode's servers are down

You are to write a method in the class Solution with the following prototype:

long long zeroFilledSubarray(vector<int>& nums);

You are given an array of up to 100,000 numbers.
You are to return the number of subarrays of the array that contain only zeros.
A subarray is a sequence of elements with contiguous indices. So, for example, if the array is [ 1, 2, 3, 4 ], then there are 10 subarrays:
- [ 1 ]
- [ 2 ]
- [ 3 ]
- [ 4 ]
- [ 1,2 ]
- [ 2,3 ]
- [ 3,4 ]
- [ 1,2,3 ]
- [ 2,3,4 ]
- [ 1,2,3,4 ]

Examples

#1: Input is [ 1, 3, 0, 0, 2, 0, 0, 4 ].
    Answer is 6.  There are four [ 0 ] subarrays, and two [ 0, 0 ] subarrays.

#2: Input is [ 0, 0, 0, 2, 0, 0 ].
    Answer is 9.  There are five [ 0 ] subarrays, three [ 0, 0 ] subarrays and one [ 0, 0, 0 ] subarray.

#3: Input is [ 2, 10, 2019 ].
    Answer is 0.

The skeleton program

The skeleton simply reads numbers on standard input, and then prints the answer. Of course, since it's a skeleton, there is no implementation -- zeroFilledSubarray() just returns zero. But it lets us compile and test:

UNIX> g++ Skeleton.cpp
UNIX> echo 1 3 0 0 2 0 0 4 | ./a.out
0
UNIX>

Step One -- Find the Contiguous Zeroes

As always, we work incrementally. Let's first find the contiguous zeros in the array. When we discover a sequence of contiguous zeroes, we'll print out its size. So, for example, with the array above, we'll print that there are two sequences of two zeros.

To do this, I'm going to run through the array and maintain one variable named num_zeros. This says how many consecutive zeros there are up to and including the index. To test, we'll print num_zerosat every index of the loop. Here's the code: (in Step_one.cpp):

long long Solution::zeroFilledSubarray(vector& nums)
{
  int num_zeros;
  size_t i;

  num_zeros = 0;

  for (i = 0; i < nums.size(); i++) {
    if (nums[i] == 0) {
      num_zeros++;
    } else {
      num_zeros = 0;
    }
    cout << "Index: " << i << ". Num_Zeros: " << num_zeros << endl;
  }

  return 0;
}

We'll run it on the examples above:

UNIX> echo 1 3 0 0 2 0 0 4 | ./a.out
Index: 0. Num_Zeros: 0
Index: 1. Num_Zeros: 0
Index: 2. Num_Zeros: 1
Index: 3. Num_Zeros: 2
Index: 4. Num_Zeros: 0
Index: 5. Num_Zeros: 1
Index: 6. Num_Zeros: 2
Index: 7. Num_Zeros: 0
0
UNIX>

UNIX> echo 0 0 0 2 0 0 | ./a.out
Index: 0. Num_Zeros: 1
Index: 1. Num_Zeros: 2
Index: 2. Num_Zeros: 3
Index: 3. Num_Zeros: 0
Index: 4. Num_Zeros: 1
Index: 5. Num_Zeros: 2
0
UNIX>

UNIX> echo 2 10 2019 | ./a.out
Index: 0. Num_Zeros: 0
Index: 1. Num_Zeros: 0
Index: 2. Num_Zeros: 0
0
UNIX>

Step Two -- Counting the Subarrays

To figure out how to count the subarrays, I like to simply use examples from small to big until I see the pattern. So:

With one zero, there is one subarray.
With two zeroes, there are three subarrays (2 and 1).
With three zeroes, there are six subarrays (3 and 2 and 1).

It looks like with n zeroes, there are (n and n-1 and n-2 ... and 1) subarrays. We can calculate that with an expression n(n+1)/2. So, when we reach the end of a sequence of zeroes, we can calculate that expression. I do that in Step_Two.cpp:

long long Solution::zeroFilledSubarray(vector<int>& nums)
{
  int num_zeros;
  size_t i;
  long long rv;

  num_zeros = 0;
  rv = 0;
  nums.push_back(1);       // Make sure we always end with a non-zero.

  for (i = 0; i < nums.size(); i++) {
    if (nums[i] == 0) {
      num_zeros++;
    } else {
      rv += (num_zeros*(num_zeros+1)/2);
      num_zeros = 0;
    }
  }
 
  return rv;
}

You'll note, I put an extra 1 at the end of nums. That's because I count the subarrays when I first see a non-zero, and this way I don't need any special code to handle the case when nums ends with a zero. That's called a sentinel, and you'll see it a lot from me.

UNIX> echo 1 3 0 0 2 0 0 4 | ./a.out
6
UNIX> echo 0 0 0 2 0 0 | ./a.out
9
UNIX> echo 2 10 2019 | ./a.out
0
UNIX>

Submit? Not yet -- let's make sure it works for the largest array size -- let's create a file in vim with 100,000 lines, where each line is a zero, and make sure it works. It should equal (100,000*100,001)/2 = 5000050000.

UNIX> vi test.txt                 # Create the file with 100,000 zeroes.
UNIX> head -n 1 test.txt          # The first line is a zero.
0
UNIX> tail -n 1 test.txt          # The last line is a zero.
0
UNIX> wc test.txt                 # It is 100,000 lines.
  100000  100000  200000 test.txt
UNIX> sort -u test.txt            # And each line is a zero
0
UNIX> ./a.out < test.txt          # And it fails.
705082704
UNIX>

Why did it fail? Because num_zeros is an int, and we have overflow. Change num_zeros to a long long and we're all good. That's done in Step_Three.cpp.

UNIX> diff Step_Two.cpp Step_Three.cpp         # The only difference is changing the type of num_zeros to a long long
22c22
<   int num_zeros;
---
>   long long num_zeros;
UNIX> ./a.out < test.txt                       # And it works.
5000050000
UNIX>

There's an easier way

As it turns out, when you add the i-th zero, it adds i subarrays. So you can make your code even easier (in Easier.cpp)

long long Solution::zeroFilledSubarray(vector<int>& nums)
{
  long long num_zeros;
  size_t i;
  long long rv;

  num_zeros = 0;
  rv = 0;

  for (i = 0; i < nums.size(); i++) {
    if (nums[i] == 0) {
      num_zeros++;
    } else {
      num_zeros = 0;
    }
    rv += num_zeros;
  }
 
  return rv;
}