Number of Zero-Filled Subarrays

medium array math

Problem

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.

Inputnums = [1, 3, 0, 0, 2, 0, 0, 4]

Output6

Two zero runs of length 2 each. Each contributes 2·3/2 = 3 subarrays. Total = 6.

nums (comma-separated)

def zero_filled_subarray(nums):
    total = 0
    run = 0
    for x in nums:
        if x == 0:
            run += 1
            total += run
        else:
            run = 0
    return total

function zeroFilledSubarray(nums) {
  let total = 0;
  let run = 0;
  for (const x of nums) {
    if (x === 0) {
      run += 1;
      total += run;
    } else {
      run = 0;
    }
  }
  return total;
}

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        long total = 0;
        long run = 0;
        for (int x : nums) {
            if (x == 0) {
                run += 1;
                total += run;
            } else {
                run = 0;
            }
        }
        return total;
    }
}

long long zeroFilledSubarray(vector<int>& nums) {
    long long total = 0;
    long long run = 0;
    for (int x : nums) {
        if (x == 0) {
            run += 1;
            total += run;
        } else {
            run = 0;
        }
    }
    return total;
}

Explanation

We need to count every contiguous block made only of zeros. The slick way is a single left-to-right pass that tracks how long the current run of zeros is.

Here is the key idea: whenever we land on a zero and the current run length becomes run, that zero is the right end of exactly run new all-zero subarrays (the ones ending right here, of lengths 1 up to run). So we add run to total at every zero.

If we hit a non-zero, the streak is broken, so we reset run = 0 and keep going.

Example: nums = [1, 3, 0, 0, 2, 0, 0, 4]. The first 0 makes run = 1 (add 1), the next 0 makes run = 2 (add 2). Then a non-zero resets it. The later pair of zeros adds 1 + 2 = 3 again. Total = 3 + 3 = 6.

Adding run each step is just a quiet way of summing 1 + 2 + ... + r for every run, which equals r*(r+1)/2 — without ever computing that formula directly.

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