LeetCode 2348 - Number of Zero-Filled Subarrays

The problem asks us to count the number of contiguous subarrays in an integer array nums that consist entirely of zeros. A subarray is defined as any consecutive sequence of elements from the original array.

leetcodemediumarraymath

LeetCode Problem 2348

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to count the number of contiguous subarrays in an integer array nums that consist entirely of zeros. A subarray is defined as any consecutive sequence of elements from the original array. The input array can contain any integers within the range -10^9 to 10^9, and the array length can be up to 10^5, which is significant because it rules out algorithms with quadratic or higher complexity.

The output is a single integer representing the total number of subarrays composed only of zeros. Each contiguous sequence of zeros contributes multiple subarrays. For example, a sequence of length k zeros contributes 1 + 2 + ... + k = k*(k+1)/2 subarrays.

Important edge cases include arrays with no zeros at all, arrays with all zeros, and sequences of zeros appearing at the start or end of the array. The problem guarantees at least one element in the array, so empty input does not need to be handled.

Approaches

The brute-force approach involves checking every possible subarray in the array and counting it if all elements are zero. Specifically, one could use nested loops: the outer loop starts the subarray at index i, and the inner loop extends the subarray to index j while checking if all elements from i to j are zero. While this method is correct, it is too slow for large arrays because it has O(n^2) time complexity in the worst case, where n is the length of the array.

The optimal approach relies on the observation that zeros form contiguous blocks. Instead of checking all subarrays individually, we can count the length of each contiguous zero block. If a zero block has length k, the number of zero-filled subarrays it contributes is k*(k+1)/2. We iterate through the array once, maintaining a running count of consecutive zeros, adding the count of subarrays ending at each zero to the result. When a non-zero element is encountered, we reset the running count. This approach is linear in time and uses constant space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check all possible subarrays, too slow for large arrays
Optimal O(n) O(1) Count contiguous zero blocks and sum subarrays efficiently

Algorithm Walkthrough

  1. Initialize two variables: total to store the cumulative count of zero-filled subarrays and current_zeros to store the length of the current contiguous zero block.
  2. Iterate through each element in the array nums.
  3. If the current element is 0, increment current_zeros by 1. Add current_zeros to total. This works because a zero at index i extends all previous zero subarrays by one, and also counts the subarray consisting of just this zero.
  4. If the current element is non-zero, reset current_zeros to 0.
  5. Continue this process until the end of the array.
  6. Return total.

Why it works: Each zero in a contiguous sequence contributes to multiple subarrays, and the running count current_zeros captures this incremental contribution. By summing current_zeros at each step, we account for all possible zero-filled subarrays.

Python Solution

from typing import List

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        total = 0
        current_zeros = 0
        for num in nums:
            if num == 0:
                current_zeros += 1
                total += current_zeros
            else:
                current_zeros = 0
        return total

The code iterates through the array once. For each zero, it increments the current_zeros counter and adds it to total. For non-zero elements, the counter is reset. This directly implements the optimal approach, efficiently counting all zero-filled subarrays.

Go Solution

func zeroFilledSubarray(nums []int) int64 {
    var total int64 = 0
    var currentZeros int64 = 0
    for _, num := range nums {
        if num == 0 {
            currentZeros += 1
            total += currentZeros
        } else {
            currentZeros = 0
        }
    }
    return total
}

In Go, we use int64 for total and currentZeros to handle large sums without overflow. The loop logic mirrors the Python solution, iterating through each element and incrementally counting zero-filled subarrays.

Worked Examples

Example 1: nums = [1,3,0,0,2,0,0,4]

Index num current_zeros total
0 1 0 0
1 3 0 0
2 0 1 1
3 0 2 3
4 2 0 3
5 0 1 4
6 0 2 6
7 4 0 6

Result: 6

Example 2: nums = [0,0,0,2,0,0]

Index num current_zeros total
0 0 1 1
1 0 2 3
2 0 3 6
3 2 0 6
4 0 1 7
5 0 2 9

Result: 9

Example 3: nums = [2,10,2019]

All elements are non-zero, so total remains 0. Result: 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array of length n
Space O(1) Only two integer counters are used regardless of input size

The optimal algorithm achieves linear time because it does not require nested loops or storing additional structures; each element is processed exactly once. Space complexity is constant because we only need counters, not auxiliary arrays or hash maps.

Test Cases

# provided examples
assert Solution().zeroFilledSubarray([1,3,0,0,2,0,0,4]) == 6  # mixed zeros and non-zeros
assert Solution().zeroFilledSubarray([0,0,0,2,0,0]) == 9      # multiple zero blocks
assert Solution().zeroFilledSubarray([2,10,2019]) == 0        # no zeros

# edge cases
assert Solution().zeroFilledSubarray([0]) == 1                # single zero
assert Solution().zeroFilledSubarray([1]) == 0                # single non-zero
assert Solution().zeroFilledSubarray([0,0,0,0,0]) == 15      # all zeros
assert Solution().zeroFilledSubarray([1,0,0,0,1,0]) == 6     # zeros at middle and end
assert Solution().zeroFilledSubarray([1,2,3,4,5]) == 0       # no zeros
Test Why
[1,3,0,0,2,0,0,4] Typical mixed zeros and non-zeros
[0,0,0,2,0,0] Multiple contiguous zero blocks
[2,10,2019] No zeros at all
[0] Single element zero
[1] Single element non-zero
[0,0,0,0,0] All zeros
[1,0,0,0,1,0] Zeros at middle and end of array
[1,2,3,4,5] No zeros, stress test for counting logic

Edge Cases

One important edge case is a single-element array. If the element is zero, the function should return 1; if it is non-zero, the function should return 0. The implementation handles this by simply following the same iteration logic.

Another edge case is an array composed entirely of zeros. This can produce a large number of subarrays, up to n*(n+1)/2. Using a running counter ensures the algorithm counts all subarrays correctly without storing them explicitly.

A third edge case is zeros appearing at the start or end of the array. Because we reset the counter only when encountering non-zero elements, sequences of zeros at either end are counted correctly, maintaining correctness in all positions.