Problem Description

Given an integer array nums, you need to count the total number of subarrays that contain only zeros.

A subarray is defined as a contiguous sequence of elements from the array. For example, if you have an array [1, 0, 0, 2, 0], the subarrays filled with only zeros would be: [0] at index 1, [0] at index 2, [0, 0] from indices 1-2, and [0] at index 4.

The key insight is that when you have n consecutive zeros, the number of all-zero subarrays you can form from them is n * (n + 1) / 2. This is because:

• You can have n subarrays of length 1
• You can have n-1 subarrays of length 2
• You can have n-2 subarrays of length 3
• And so on...

The solution tracks consecutive zeros using a counter cnt. When encountering a zero, it increments cnt and adds cnt to the answer. This works because at each zero position, the number of all-zero subarrays ending at that position equals the count of consecutive zeros up to that point. When a non-zero element is encountered, the counter resets to 0.

For example, with array [0, 0, 0, 2, 0, 0]:

• At first 0: cnt = 1, add 1 to answer
• At second 0: cnt = 2, add 2 to answer (subarrays: [0] and [0,0])
• At third 0: cnt = 3, add 3 to answer (subarrays: [0], [0,0], and [0,0,0])
• At 2: reset cnt = 0
• At fourth 0: cnt = 1, add 1 to answer
• At fifth 0: cnt = 2, add 2 to answer

Total: 1 + 2 + 3 + 1 + 2 = 9 all-zero subarrays.

Intuition

When we encounter a sequence of consecutive zeros, we need to think about how many subarrays we can form. Let's build up the intuition step by step.

Consider a single zero [0] - it forms exactly 1 subarray.

Now consider two consecutive zeros [0, 0]:

• The first zero by itself: [0]
• The second zero by itself: [0]
• Both zeros together: [0, 0]
• Total: 3 subarrays

For three consecutive zeros [0, 0, 0]:

• Single-element subarrays: [0], [0], [0] (3 subarrays)
• Two-element subarrays: [0, 0], [0, 0] (2 subarrays)
• Three-element subarray: [0, 0, 0] (1 subarray)
• Total: 6 subarrays

Notice the pattern: for n consecutive zeros, we get 1 + 2 + 3 + ... + n = n * (n + 1) / 2 subarrays.

But instead of finding all groups of consecutive zeros and then calculating using the formula, we can use a clever observation: when we're at the k-th zero in a sequence of consecutive zeros, the number of all-zero subarrays ending at this position is exactly k.

Why? Because from this position, we can form:

• A subarray with just this zero: 1 way
• A subarray with this zero and the previous zero: 1 way (if there's a previous zero)
• A subarray with this zero and the previous two zeros: 1 way (if there are two previous zeros)
• And so on...

This means as we traverse the array and maintain a counter of consecutive zeros, each time we see a new zero, we increment our counter and add that counter value to our total. When we hit a non-zero element, we reset the counter. This approach naturally accumulates the sum 1 + 2 + 3 + ... for each group of consecutive zeros, giving us the correct total count.

Learn more about Math patterns.

Solution Approach

The implementation uses a simple traversal with a counting technique. We maintain two variables:

• ans: Accumulates the total count of all-zero subarrays
• cnt: Tracks the current number of consecutive zeros

The algorithm works as follows:

1. Initialize counters: Start with both ans and cnt set to 0.

2. Traverse the array: For each element x in nums:

   • If x is 0:
     • Increment cnt by 1 (extending the current sequence of zeros)
     • Add cnt to ans (all subarrays ending at current position)
   • If x is not 0:
     • Reset cnt to 0 (breaking the sequence of consecutive zeros)

3. Return the result: After traversing the entire array, ans contains the total count.

The key insight is that when we're at the k-th consecutive zero, there are exactly k all-zero subarrays ending at that position. By adding cnt to our answer each time we encounter a zero, we're effectively computing the sum 1 + 2 + 3 + ... + n for each group of n consecutive zeros.

Example walkthrough with nums = [1, 0, 0, 0, 2, 0]:

• Index 0: x = 1, non-zero → cnt = 0, ans = 0
• Index 1: x = 0 → cnt = 1, ans = 0 + 1 = 1
• Index 2: x = 0 → cnt = 2, ans = 1 + 2 = 3
• Index 3: x = 0 → cnt = 3, ans = 3 + 3 = 6
• Index 4: x = 2, non-zero → cnt = 0, ans = 6
• Index 5: x = 0 → cnt = 1, ans = 6 + 1 = 7

Time Complexity: O(n) where n is the length of the array, as we traverse the array once.

Space Complexity: O(1) as we only use two variables regardless of input size.

This approach is similar to problems involving counting arithmetic sequences or consecutive elements, where maintaining a running count allows us to efficiently calculate the total without explicitly finding all subarrays.

Example Walkthrough

Let's walk through the solution with a small example: nums = [0, 0, 1, 0, 0, 0]

We'll maintain two variables:

• cnt: tracks consecutive zeros
• ans: accumulates total count of all-zero subarrays

Step-by-step execution:

Index 0: nums[0] = 0

• Since it's a zero, increment cnt: cnt = 1
• Add cnt to answer: ans = 0 + 1 = 1
• This counts the subarray [0]

Index 1: nums[1] = 0

• Since it's a zero, increment cnt: cnt = 2
• Add cnt to answer: ans = 1 + 2 = 3
• This counts 2 new subarrays ending at index 1: [0] (just index 1) and [0,0] (indices 0-1)

Index 2: nums[2] = 1

• Since it's non-zero, reset cnt: cnt = 0
• Answer remains: ans = 3

Index 3: nums[3] = 0

• Since it's a zero, increment cnt: cnt = 1
• Add cnt to answer: ans = 3 + 1 = 4
• This counts the subarray [0]

Index 4: nums[4] = 0

• Since it's a zero, increment cnt: cnt = 2
• Add cnt to answer: ans = 4 + 2 = 6
• This counts 2 new subarrays ending at index 4: [0] (just index 4) and [0,0] (indices 3-4)

Index 5: nums[5] = 0

• Since it's a zero, increment cnt: cnt = 3
• Add cnt to answer: ans = 6 + 3 = 9
• This counts 3 new subarrays ending at index 5: [0] (just index 5), [0,0] (indices 4-5), and [0,0,0] (indices 3-5)

Final result: ans = 9

We can verify this is correct by listing all 9 all-zero subarrays:

1. [0] at index 0
2. [0] at index 1
3. [0,0] from indices 0-1
4. [0] at index 3
5. [0] at index 4
6. [0,0] from indices 3-4
7. [0] at index 5
8. [0,0] from indices 4-5
9. [0,0,0] from indices 3-5

The algorithm efficiently counts these without explicitly generating them, using the insight that at each zero position, the number of all-zero subarrays ending there equals the count of consecutive zeros up to that point.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once, performing constant-time operations (comparisons, additions, and assignments) for each element.

Space Complexity: O(1). The algorithm only uses two additional variables (ans and cnt) to track the result and the current count of consecutive zeros, regardless of the input size. No additional data structures are created that scale with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Mathematical Formula Approach

A common alternative approach is to find groups of consecutive zeros and apply the formula n * (n + 1) / 2 for each group. However, this can lead to integer overflow issues in languages with fixed integer sizes when dealing with very large consecutive zero sequences.

Problematic approach:

def zeroFilledSubarray(nums):
    total = 0
    count = 0
  
    for num in nums:
        if num == 0:
            count += 1
        else:
            if count > 0:
                # Potential overflow for large count values
                total += count * (count + 1) // 2
                count = 0
  
    # Don't forget the last group!
    if count > 0:
        total += count * (count + 1) // 2
  
    return total

Issues with this approach:

• For very large values of count, count * (count + 1) might overflow before division
• Easy to forget handling the last group of zeros if the array ends with zeros

Solution: The incremental approach in the provided solution avoids this by adding smaller values incrementally rather than computing large products.

2. Off-by-One Errors When Counting Subarrays

Some might try to manually track start and end indices of zero sequences, leading to off-by-one errors in counting subarrays.

Incorrect approach:

def zeroFilledSubarray(nums):
    total = 0
    start = -1
  
    for i, num in enumerate(nums):
        if num == 0:
            if start == -1:
                start = i
        else:
            if start != -1:
                # Wrong calculation - might miss subarrays
                length = i - start  # Should be i - start, but logic is flawed
                total += length * (length + 1) // 2
                start = -1
  
    return total

Solution: The incremental counting approach naturally handles all subarrays without explicitly tracking indices.

3. Resetting Counter at Wrong Time

A subtle mistake is resetting the counter after processing a zero instead of when encountering a non-zero element.

Incorrect implementation:

def zeroFilledSubarray(nums):
    total = 0
    count = 0
  
    for num in nums:
        if num == 0:
            count += 1
            total += count
            count = 0  # Wrong! This resets after every zero
        else:
            count = 0
  
    return total

This would only count subarrays of length 1, giving incorrect results.

Solution: Only reset the counter when encountering a non-zero element, allowing the counter to accumulate for consecutive zeros.

4. Not Understanding the Incremental Logic

Some might think they need to explicitly count all possible subarrays, leading to inefficient nested loop solutions.

Inefficient approach:

def zeroFilledSubarray(nums):
    total = 0
    n = len(nums)
  
    # O(n²) or O(n³) approach - unnecessary!
    for i in range(n):
        if nums[i] == 0:
            for j in range(i, n):
                if nums[j] != 0:
                    break
                total += 1
  
    return total

Solution: Understanding that adding the current consecutive count gives us all subarrays ending at the current position eliminates the need for nested loops.