Brute Force Approach

A naive approach would be to iterate through all possible subarrays and count those that contain only zeros. For each subarray, we check if all elements are zero, and if so, increment our counter.

Code (Python)

def count_zero_subarrays_brute_force(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            subarray = nums[i:j+1]
            if all(x == 0 for x in subarray):
                count += 1
    return count

Time Complexity

The time complexity is O(n^3) because there are O(n^2) possible subarrays, and checking if a subarray contains only zeros takes O(n) time.

Space Complexity

The space complexity is O(n) in the worst case for storing the subarray.

Optimal Approach

A more efficient approach is to iterate through the array and keep track of the consecutive zeros. When we encounter a non-zero element, we can calculate the number of subarrays formed by the previous consecutive zeros using the formula n * (n + 1) / 2, where n is the number of consecutive zeros. Then, reset the consecutive zero counter.

Code (Python)

def count_zero_subarrays_optimal(nums):
    count = 0
    consecutive_zeros = 0
    for num in nums:
        if num == 0:
            consecutive_zeros += 1
        else:
            count += consecutive_zeros * (consecutive_zeros + 1) // 2
            consecutive_zeros = 0
    count += consecutive_zeros * (consecutive_zeros + 1) // 2  # Handle trailing zeros
    return count

Time Complexity

The time complexity is O(n) because we iterate through the array only once.

Space Complexity

The space complexity is O(1) because we only use a constant amount of extra space.

Edge Cases

• Empty array: If the input array is empty, the function should return 0.
• Array with no zeros: If the array contains no zeros, the function should return 0.
• Array with only zeros: If the array contains only zeros, the function should return n * (n + 1) / 2.
• Trailing zeros: The optimal approach must handle the case where the array ends with a sequence of zeros.

Example

For nums = [0, 0, 0, 2, 0, 0], the function would work as follows:

1. consecutive_zeros = 0, count = 0
2. num = 0: consecutive_zeros = 1
3. num = 0: consecutive_zeros = 2
4. num = 0: consecutive_zeros = 3
5. num = 2: count = 3 * (3 + 1) // 2 = 6, consecutive_zeros = 0
6. num = 0: consecutive_zeros = 1
7. num = 0: consecutive_zeros = 2
8. Loop finishes: count = 6 + 2 * (2 + 1) // 2 = 6 + 3 = 9

The function returns 9.