2348. Number of Zero-Filled Subarrays - Explanation

Description

You are 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 <= 100,000
-1,000,000,000 <= nums[i] <= 1,000,000,000

Topics

Array Math

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Array Traversal - Iterating through arrays while tracking consecutive elements
Counting Subarrays - Understanding that a sequence of k consecutive elements contains k*(k+1)/2 subarrays
Arithmetic Series - Using the formula 1 + 2 + ... + k = k*(k+1)/2 to count subarrays efficiently

1. Brute Force

Intuition

The most straightforward approach is to check every possible subarray and count those filled entirely with zeros. For each starting index, we extend the subarray as long as we keep seeing zeros, incrementing our count for each valid zero-filled subarray we find.

Algorithm

Initialize a result counter res = 0.
For each starting index i from 0 to n-1:
- For each ending index j from i to n-1:
  - If nums[j] is not 0, break out of the inner loop.
  - Otherwise, increment res (we found another zero-filled subarray).
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = 0
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if nums[j] != 0:
                    break
                res += 1
        return res

public class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                if (nums[j] != 0) break;
                res++;
            }
        }
        return res;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long res = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i; j < nums.size(); j++) {
                if (nums[j] != 0) break;
                res++;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums) {
        let res = 0;
        for (let i = 0; i < nums.length; i++) {
            for (let j = i; j < nums.length; j++) {
                if (nums[j] != 0) break;
                res++;
            }
        }
        return res;
    }
}

public class Solution {
    public long ZeroFilledSubarray(int[] nums) {
        long res = 0;
        for (int i = 0; i < nums.Length; i++) {
            for (int j = i; j < nums.Length; j++) {
                if (nums[j] != 0) break;
                res++;
            }
        }
        return res;
    }
}

func zeroFilledSubarray(nums []int) int64 {
    var res int64 = 0
    for i := 0; i < len(nums); i++ {
        for j := i; j < len(nums); j++ {
            if nums[j] != 0 {
                break
            }
            res++
        }
    }
    return res
}

class Solution {
    fun zeroFilledSubarray(nums: IntArray): Long {
        var res = 0L
        for (i in nums.indices) {
            for (j in i until nums.size) {
                if (nums[j] != 0) break
                res++
            }
        }
        return res
    }
}

class Solution {
    func zeroFilledSubarray(_ nums: [Int]) -> Int {
        var res = 0
        for i in 0..<nums.count {
            for j in i..<nums.count {
                if nums[j] != 0 { break }
                res += 1
            }
        }
        return res
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums: number[]): number {
        let res = 0;
        for (let i = 0; i < nums.length; i++) {
            for (let j = i; j < nums.length; j++) {
                if (nums[j] != 0) break;
                res++;
            }
        }
        return res;
    }
}

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut res: i64 = 0;
        for i in 0..nums.len() {
            for j in i..nums.len() {
                if nums[j] != 0 { break; }
                res += 1;
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Count Consecutive Zeros - I

Intuition

Instead of checking every subarray, we can be smarter by processing consecutive groups of zeros. When we find a sequence of k consecutive zeros, the number of zero-filled subarrays within that sequence is 1 + 2 + ... + k.

We can compute this incrementally: as we extend a run of zeros by one element, we add the current run length to our total. For example, if we have seen 3 zeros so far and see a 4th, we add 4 to the count (representing the 4 new subarrays ending at this position).

Algorithm

Initialize res = 0 and index i = 0.
While i < n:
- Initialize count = 0 for the current run of zeros.
- While nums[i] == 0:
  - Increment count.
  - Add count to res (this counts all subarrays ending at the current zero).
  - Increment i.
- Increment i to skip the non-zero element.
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = i = 0
        while i < len(nums):
            count = 0
            while i < len(nums) and nums[i] == 0:
                count += 1
                i += 1
                res += count
            i += 1
        return res

public class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long res = 0;
        int i = 0;
        while (i < nums.length) {
            long count = 0;
            while (i < nums.length && nums[i] == 0) {
                count++;
                i++;
                res += count;
            }
            i++;
        }
        return res;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long res = 0;
        int i = 0;
        while (i < nums.size()) {
            long long count = 0;
            while (i < nums.size() && nums[i] == 0) {
                count++;
                i++;
                res += count;
            }
            i++;
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums) {
        let res = 0,
            i = 0;
        while (i < nums.length) {
            let count = 0;
            while (i < nums.length && nums[i] === 0) {
                count++;
                i++;
                res += count;
            }
            i++;
        }
        return res;
    }
}

public class Solution {
    public long ZeroFilledSubarray(int[] nums) {
        long res = 0;
        int i = 0;
        while (i < nums.Length) {
            long count = 0;
            while (i < nums.Length && nums[i] == 0) {
                count++;
                i++;
                res += count;
            }
            i++;
        }
        return res;
    }
}

func zeroFilledSubarray(nums []int) int64 {
    var res int64 = 0
    i := 0
    for i < len(nums) {
        var count int64 = 0
        for i < len(nums) && nums[i] == 0 {
            count++
            i++
            res += count
        }
        i++
    }
    return res
}

class Solution {
    fun zeroFilledSubarray(nums: IntArray): Long {
        var res = 0L
        var i = 0
        while (i < nums.size) {
            var count = 0L
            while (i < nums.size && nums[i] == 0) {
                count++
                i++
                res += count
            }
            i++
        }
        return res
    }
}

class Solution {
    func zeroFilledSubarray(_ nums: [Int]) -> Int {
        var res = 0
        var i = 0
        while i < nums.count {
            var count = 0
            while i < nums.count && nums[i] == 0 {
                count += 1
                i += 1
                res += count
            }
            i += 1
        }
        return res
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums: number[]): number {
        let res = 0,
            i = 0;
        while (i < nums.length) {
            let count = 0;
            while (i < nums.length && nums[i] === 0) {
                count++;
                i++;
                res += count;
            }
            i++;
        }
        return res;
    }
}

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut res: i64 = 0;
        let mut i = 0;
        while i < nums.len() {
            let mut count: i64 = 0;
            while i < nums.len() && nums[i] == 0 {
                count += 1;
                i += 1;
                res += count;
            }
            i += 1;
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Count Consecutive Zeros - II

Intuition

This is a cleaner version of the previous approach using a single loop. We maintain a running count of consecutive zeros. Each time we see a zero, we increment the count and add it to our result. Each time we see a non-zero, we reset the count to 0.

The key insight remains the same: when we are at the k-th consecutive zero, there are exactly k new zero-filled subarrays ending at this position (subarrays of length 1, 2, ..., k).

Algorithm

Initialize res = 0 and count = 0.
For each number in the array:
- If the number is 0, increment count.
- Otherwise, reset count = 0.
- Add count to res.
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = count = 0

        for num in nums:
            if num == 0:
                count += 1
            else:
                count = 0
            res += count

        return res

public class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long res = 0;
        int count = 0;

        for (int num : nums) {
            if (num == 0) {
                count++;
            } else {
                count = 0;
            }
            res += count;
        }

        return res;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long res = 0;
        int count = 0;

        for (int& num : nums) {
            if (num == 0) {
                count++;
            } else {
                count = 0;
            }
            res += count;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums) {
        let res = 0,
            count = 0;

        for (let num of nums) {
            if (num === 0) {
                count++;
            } else {
                count = 0;
            }
            res += count;
        }

        return res;
    }
}

public class Solution {
    public long ZeroFilledSubarray(int[] nums) {
        long res = 0;
        int count = 0;

        foreach (int num in nums) {
            if (num == 0) {
                count++;
            } else {
                count = 0;
            }
            res += count;
        }

        return res;
    }
}

func zeroFilledSubarray(nums []int) int64 {
    var res int64 = 0
    count := 0

    for _, num := range nums {
        if num == 0 {
            count++
        } else {
            count = 0
        }
        res += int64(count)
    }

    return res
}

class Solution {
    fun zeroFilledSubarray(nums: IntArray): Long {
        var res = 0L
        var count = 0

        for (num in nums) {
            if (num == 0) {
                count++
            } else {
                count = 0
            }
            res += count
        }

        return res
    }
}

class Solution {
    func zeroFilledSubarray(_ nums: [Int]) -> Int {
        var res = 0
        var count = 0

        for num in nums {
            if num == 0 {
                count += 1
            } else {
                count = 0
            }
            res += count
        }

        return res
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums: number[]): number {
        let res = 0,
            count = 0;

        for (let num of nums) {
            if (num === 0) {
                count++;
            } else {
                count = 0;
            }
            res += count;
        }

        return res;
    }
}

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut res: i64 = 0;
        let mut count: i64 = 0;

        for &num in &nums {
            if num == 0 {
                count += 1;
            } else {
                count = 0;
            }
            res += count;
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

4. Count Consecutive Zeros (Math)

Intuition

Instead of adding incrementally during each run of zeros, we can use the mathematical formula directly. A sequence of k consecutive zeros contains exactly k * (k + 1) / 2 zero-filled subarrays (the sum of 1 + 2 + ... + k).

We scan through the array, counting the length of each consecutive zero sequence. When a sequence ends (we hit a non-zero or reach the end), we apply the formula to add all subarrays from that sequence at once.

Algorithm

Initialize res = 0 and count = 0.
For each number in the array:
- If the number is 0, increment count.
- Otherwise:
  - Add count * (count + 1) / 2 to res.
  - Reset count = 0.
After the loop, add the final count * (count + 1) / 2 to handle any trailing zeros.
Return res.

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        res = count = 0
        for num in nums:
            if num == 0:
                count += 1
            else:
                res += (count * (count + 1)) // 2
                count = 0
        res += (count * (count + 1)) // 2
        return res

public class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long res = 0, count = 0;
        for (int num : nums) {
            if (num == 0) {
                count++;
            } else {
                res += count * (count + 1) / 2;
                count = 0;
            }
        }
        res += count * (count + 1) / 2;
        return res;
    }
}

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long res = 0, count = 0;
        for (int num : nums) {
            if (num == 0) {
                count++;
            } else {
                res += count * (count + 1) / 2;
                count = 0;
            }
        }
        res += count * (count + 1) / 2;
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums) {
        let res = 0,
            count = 0;
        for (let num of nums) {
            if (num === 0) {
                count++;
            } else {
                res += (count * (count + 1)) / 2;
                count = 0;
            }
        }
        res += (count * (count + 1)) / 2;
        return res;
    }
}

public class Solution {
    public long ZeroFilledSubarray(int[] nums) {
        long res = 0, count = 0;
        foreach (int num in nums) {
            if (num == 0) {
                count++;
            } else {
                res += count * (count + 1) / 2;
                count = 0;
            }
        }
        res += count * (count + 1) / 2;
        return res;
    }
}

func zeroFilledSubarray(nums []int) int64 {
    var res, count int64 = 0, 0
    for _, num := range nums {
        if num == 0 {
            count++
        } else {
            res += count * (count + 1) / 2
            count = 0
        }
    }
    res += count * (count + 1) / 2
    return res
}

class Solution {
    fun zeroFilledSubarray(nums: IntArray): Long {
        var res = 0L
        var count = 0L
        for (num in nums) {
            if (num == 0) {
                count++
            } else {
                res += count * (count + 1) / 2
                count = 0
            }
        }
        res += count * (count + 1) / 2
        return res
    }
}

class Solution {
    func zeroFilledSubarray(_ nums: [Int]) -> Int {
        var res = 0
        var count = 0
        for num in nums {
            if num == 0 {
                count += 1
            } else {
                res += count * (count + 1) / 2
                count = 0
            }
        }
        res += count * (count + 1) / 2
        return res
    }
}

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    zeroFilledSubarray(nums: number[]): number {
        let res = 0,
            count = 0;
        for (let num of nums) {
            if (num === 0) {
                count++;
            } else {
                res += (count * (count + 1)) / 2;
                count = 0;
            }
        }
        res += (count * (count + 1)) / 2;
        return res;
    }
}

impl Solution {
    pub fn zero_filled_subarray(nums: Vec<i32>) -> i64 {
        let mut res: i64 = 0;
        let mut count: i64 = 0;
        for &num in &nums {
            if num == 0 {
                count += 1;
            } else {
                res += count * (count + 1) / 2;
                count = 0;
            }
        }
        res += count * (count + 1) / 2;
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Using Int Instead of Long for the Result

With an array of up to 10^5 elements, a long sequence of zeros (say, all zeros) would contribute n * (n + 1) / 2 subarrays, which can exceed 2^31 - 1. In Java and C++, using int for the result causes overflow. Always use long or long long for the result variable.

Forgetting to Handle Trailing Zeros in the Math Approach

When using the formula count * (count + 1) / 2 to count subarrays in each zero sequence, you must apply the formula one final time after the loop ends to handle any trailing zeros. A common bug is only applying the formula when hitting a non-zero element, missing the last zero sequence if the array ends with zeros.

Resetting Count at the Wrong Time

In the incremental approach, the count must be reset to 0 when encountering a non-zero element. A common mistake is resetting count before adding to the result, or forgetting to reset entirely, which causes zero sequences to be incorrectly merged across non-zero elements.