Skip to main content
Talentd

Number of Zero-Filled Subarrays - Solution & Explanation

MediumArrayMath15 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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.

 

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 <= 105
  • -109 <= nums[i] <= 109

Approach Overview

Problem Overview: Given an integer array nums, count how many subarrays contain only zeros. A valid subarray must consist entirely of 0 values and can be any contiguous portion of the array.

The key observation: zero-filled subarrays only come from contiguous blocks of zeros. If a block contains k zeros, it contributes multiple subarrays of different lengths.

Approach 1: Contiguous Zero Segment Counting (O(n) time, O(1) space)

Scan the array and identify contiguous segments of zeros. Suppose a segment contains k zeros. The number of subarrays that can be formed from that segment equals k * (k + 1) / 2. This works because each position can start a subarray and extend through the remaining zeros. For example, a run of 3 zeros produces subarrays: [0], [0], [0], [0,0], [0,0], and [0,0,0]. Iterate through the array, track the length of each zero run, compute the formula when the run ends, and add it to the total. This approach relies only on sequential traversal of the array and a simple combinatorial formula from math. Time complexity is O(n) because each element is visited once, and space complexity is O(1).

Approach 2: Running Zero Count Accumulation (O(n) time, O(1) space)

Instead of computing the contribution of a whole segment at once, accumulate it incrementally. Maintain a variable zeroCount representing the current streak of consecutive zeros. While iterating through the array, if the current value is zero, increment zeroCount and add it directly to the result. If the value is non‑zero, reset zeroCount to zero. The intuition: when you extend a zero streak, every new zero creates additional subarrays ending at the current index. For example, the third zero in a streak contributes three new subarrays ending there. This approach still performs a single pass through the array, but avoids explicitly calculating segment lengths. Time complexity remains O(n) with O(1) auxiliary space.

Recommended for interviews: The running accumulation approach is usually preferred. It shows you recognize how subarrays grow dynamically and can compute the result during iteration. The contiguous segment method also works and clearly demonstrates the combinatorial insight (k * (k + 1) / 2). In interviews, explaining the segment formula first and then implementing the running count version often shows stronger problem‑solving depth.

Approach 1: Approach 1: Count zero subarrays using a contiguous segments approach

This approach involves iterating through the array and counting the length of contiguous segments of zeros. For each segment of zeros with length n, the total number of zero-filled subarrays is the sum of the first n natural numbers.

For a segment with length n, the number of zero-filled subarrays is (n * (n + 1)) / 2. This formula is derived from the well-known sum formula for the first n integers.

The C solution iterates over the array, increasing the count for each contiguous zero encountered and adds the current count to the total subarrayCount anytime zeros[i] != 0 is encountered.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the size of the input array. This is because we only traverse the array once.

Space Complexity: O(1), since we only use a constant number of extra variables.

Try this approach in the editor →

Approach 2: Approach 2: Accumulative count of zero subarrays

This approach is slightly variation. We keep track of the number of zero subarrays as we proceed through the array. Whenever a zero is encountered, the count of zero subarrays ending at that position is incremented by the number of zero subarrays ending at the previous position plus one. When a non-zero is encountered, we reset our counter.

A variation of the simple count, where we keep another variable zeroEndsHere which tracks ongoing segments of zeros. This accumulates into count as the loop progresses.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - traversing each element once to compute the solution.

Space Complexity: O(1) - using only a few extra integer variables for tracking.

Try this approach in the editor →

Approach 3: Traversal and Counting

We traverse the array nums and use a variable cnt to record the current number of consecutive 0s. For the current element x we are traversing, if x is 0, then cnt is incremented by 1, and the number of all-zero subarrays ending with the current x is cnt, which we add to the answer. Otherwise, we set cnt to 0.

After the traversal, we return the answer.

Time complexity O(n), where n is the length of the array nums. Space complexity O(1).

Similar problems:

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Count zero subarrays using a contiguous segments approach

Time Complexity: O(n), where n is the size of the input array. This is because we only traverse the array once.

Space Complexity: O(1), since we only use a constant number of extra variables.

Approach 2: Accumulative count of zero subarrays

Time Complexity: O(n) - traversing each element once to compute the solution.

Space Complexity: O(1) - using only a few extra integer variables for tracking.

Traversal and Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Contiguous Zero Segment CountingO(n)O(1)When you want a clear mathematical explanation using the k*(k+1)/2 formula for each zero block
Running Zero Count AccumulationO(n)O(1)Best for interviews and clean implementations that compute results during a single pass

Video Solution

Number of Zero-Filled Subarrays - Leetcode 2348 - Python • NeetCodeIO • 16,790 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Zero-Filled Subarrays easy or hard?
The problem is rated Medium on LeetCode but often feels easier once the contiguous zero insight is recognized. Beginners may attempt nested loops initially, but the optimal O(n) solution comes from understanding how zero streaks generate multiple subarrays.
Number of Zero-Filled Subarrays Python/Java solution
Both Python and Java implementations typically follow the running zero-count technique. Maintain a variable tracking consecutive zeros, add it to the result whenever another zero appears, and reset when a non-zero element occurs. The algorithm runs in O(n) time and uses constant extra space.
How to solve Number of Zero-Filled Subarrays in O(n)?
Traverse the array while maintaining a counter for consecutive zeros. If the current element is zero, increment the counter and add it to the total number of subarrays. If the element is non‑zero, reset the counter to zero. This works because each additional zero extends all existing zero subarrays ending at the current index.
What is the best approach for Number of Zero-Filled Subarrays?
The most practical approach uses a running count of consecutive zeros while scanning the array once. Each time a zero appears, increment the streak and add it to the result. This counts all subarrays ending at that position. The method runs in O(n) time with O(1) space and avoids explicitly computing segment lengths.
Is Number of Zero-Filled Subarrays asked at Google/Amazon/Meta?
This pattern appears in interviews at companies like Amazon and Google where candidates must count subarrays or analyze contiguous segments. Variations often involve counting subarrays with specific values or constraints. Recognizing streak-based counting is a common expectation.
What data structure is used in Number of Zero-Filled Subarrays?
The problem primarily uses array traversal and simple integer counters. No advanced data structures like heaps or hash maps are required. The logic relies on tracking contiguous zero streaks and applying a mathematical counting principle.
What is the time complexity of Number of Zero-Filled Subarrays?
The optimal solutions run in O(n) time because the array is traversed once. Each element contributes constant work—either incrementing a zero streak or resetting it. Space complexity is O(1) since only a few counters are maintained.

Ready to solve this problem?

Practice Number of Zero-Filled Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Arithmetic Slices

Next

Find Consecutive Integers from a Data Stream