Number of Zero-Filled Subarrays

Given an integer array nums, return the number of subarrays filled with 0. A subarray is a contiguous non-empty part of the array. This is LeetCode 2348.

Example 1
Input: nums = [1, 3, 0, 0, 2, 0, 0, 4]
Output: 6
Explanation: [0] appears 4 times and [0, 0] twice.
Example 2
Input: nums = [0, 0, 0, 2, 0, 0]
Output: 9
Explanation: the run of three gives 6 and the run of two gives 3.
Example 3
Input: nums = [2, 10, 2019]
Output: 0

How to Think About It

Step 1: Count by where the subarray ends

Look at a position holding 0 that is the r-th zero of its current run of zeros. The all-zero subarrays ending there start at any of those r zeros, so there are exactly r of them.

Step 2: Keep a running run length

Walk the array. On a 0, add one to run and add run to the answer. On anything else, reset run to 0.

A run of length L then contributes 1 + 2 + ... + L = L(L + 1) / 2, which matches example 2: 6 for three zeros, 3 for two.

Step 3: Use long

An array of 105 zeros has about 5 × 109 such subarrays, which is too large for an int.

Walkthrough

nums = [0, 0, 0, 2, 0, 0].

ValuerunAddedTotal
0111
0223
0336
2006
0117
0229

Java Solution

A single loop with two variables.

Java
public class NumberOfZeroFilledSubarrays {

    public static long zeroFilledSubarray(int[] nums) {
        long count = 0;
        long run = 0;                         // length of the current run of zeros
        for (int x : nums) {
            if (x == 0) {
                run++;
                count += run;                 // run new subarrays end at this zero
            } else {
                run = 0;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(zeroFilledSubarray(new int[] {1, 3, 0, 0, 2, 0, 0, 4}));   // 6
        System.out.println(zeroFilledSubarray(new int[] {0, 0, 0, 2, 0, 0}));         // 9
        System.out.println(zeroFilledSubarray(new int[] {2, 10, 2019}));              // 0
    }
}

The original implementation, NumberOfZeroFilledSubArrays.java, is on GitHub.

Complexity

  • Time: O(n).
  • Space: O(1).

Counting subarrays by their end position is also how Subarray Sum Equals K works.