Number of Zero-Filled Subarrays

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.

Constraints:

• 1 ≤ nums.length ≤ 10^5
• -10^9 ≤ nums[i] ≤ 10^9

Since the maximum size is 10^5, your algorithm should ideally run in about O(n) or O(n log n) time to the efficient because something like O(n^2) will give TLE.

LeetCode:

2348. Number of 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.
There are 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, 1999]
Output: 0

Explanation: There is no subarray filled with 0. Therefore, we return 0.

Different Approaches

Brute Force Approach (TLE)

Intuition:

Generate all subarrays and check if they are filled with 0.

Code:

#include <bits/stdc++.h>
using namespace std;

long long zeroFilledSubarray(vector<int>& nums) {
    long long count = 0;
    int n = nums.size();

    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            bool allZero = true;
            for (int k = i; k <= j; k++) {
                if (nums[k] != 0) {
                    allZero = false;
                    break;
                }
            }
            if (allZero) count++;
        }
    }
    return count;
}

Complexity Analysis:

• Time Complexity:O(n^3)
• Space Complexity:O(1)

2️⃣ Better Brute Force Approach

• Avoid re-checking the inner loop.
• As we expand a subarray, if the current element is 0, we extend the zero subarray count; otherwise, reset.

Code:

#include <bits/stdc++.h>
using namespace std;

long long zeroFilledSubarray(vector<int>& nums) {
    long long count = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        long long zeros = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] == 0) {
                zeros++;
                count++;
            } else {
                break; // stop, as subarray no longer all zeros
            }
        }
    }
    return count;
}

Complexity Analysis:

• Time Complexity:O(n^2)
• Space Complexity:O(1)

3️⃣ Optimal Approach (Mathematical / Counting)

Intuition:

• Traverse the array once.
• Keep track of current streak of zeroes.
• For each element:
  • If it's 0, extend streak -> add streak length to result.
  • If it's nonzero, reset streak.

Code:

#include <bits/stdc++.h>
using namespace std;

long long zeroFilledSubarray(vector<int>& nums) {
    long long count = 0, streak = 0;
    for (int num : nums) {
        if (num == 0) {
            streak++;
            count += streak; // add new subarrays ending here
        } else {
            streak = 0;
        }
    }
    return count;
}

Complexity Analysis:

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