AlgoInsight

DSA problem

Number of Zero-Filled Subarrays

MediumArraysPattern: Counting Subarraystop300AmazonGoogleMicrosoftAdobe

Given an integer array nums, return the number of subarrays filled with 0.

A subarray is a contiguous non-empty sequence of elements within an array.

The key insight is that a single contiguous run of k consecutive zeros contributes k * (k + 1) / 2 zero-filled subarrays, because for a run of length k there are k subarrays ending at the last zero, plus all those counted for the prefix runs. By tracking the length of the current consecutive-zero streak and accumulating it as we scan, we can compute the total in a single pass.

For example, the array [1, 3, 0, 0, 2, 0, 0, 4] has two zero runs of length 2 each, contributing 3 + 3 = 6 zero-filled subarrays.

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. The total number of zero-filled subarrays is 4 + 2 = 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. The total number of zero-filled subarrays is 5 + 3 + 1 = 9.
Example 3
Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

arraycountingmath

Browse all DSA problems