665. Number of Zero-Filled Subarrays
You are given an integer array nums. Count how many subarrays of nums are filled entirely with zeros, and return that count.
A subarray is a contiguous, non-empty slice of the array. Two subarrays with the same values but different positions count separately — you are counting occurrences, not distinct contents.
With n up to 10^5 the answer can exceed a 32-bit integer, so return it in a 64-bit type.
Example 1:
Input: nums = [4, 0, 0, 0, 7]
Output: 6
Explanation: The zeros form one run of length 3, which contains three [0] subarrays, two [0,0] subarrays, and one [0,0,0] — 3 + 2 + 1 = 6.
Example 2:
Input: nums = [0, 0, 1, 0]
Output: 4
Explanation: The run of two zeros contributes 2 + 1 = 3 subarrays; the lone trailing zero contributes 1 more. Nothing spanning the 1 can count.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
Hints:
Enumerating every (start, end) pair and checking it is O(n²) or worse. Notice that a zero-filled subarray can never cross a non-zero element.
So the answer only depends on the maximal runs of consecutive zeros. A run of length k contains k + (k-1) + … + 1 = k(k+1)/2 zero-filled subarrays.
Even simpler, count subarrays by their right endpoint: keep a running streak of consecutive zeros ending at i. Each position adds `streak` new subarrays (one per possible start inside the run). One pass, O(1) extra space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 0, 0, 0, 7]
Expected output: 6