Number of Zero-Filled Subarrays
Given an integer array nums
Example 1
Output: 6
Explanation: [0] appears 4 times and [0, 0] twice.
Example 2
Output: 9
Explanation: the run of three gives 6 and the run of two gives 3.
Example 3
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 runrunrun
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]
| Value | run | Added | Total |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 0 | 2 | 2 | 3 |
| 0 | 3 | 3 | 6 |
| 2 | 0 | 0 | 6 |
| 0 | 1 | 1 | 7 |
| 0 | 2 | 2 | 9 |
Java Solution
A single loop with two variables.
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,
Complexity
- Time: O(n).
- Space: O(1).
Counting subarrays by their end position is also how