NeetCode #136LC-2348MediumArrays & Hashing
← Back to All Problems#136 · #2348 · Number of Zero-Filled Subarrays(全 0 子数组的数目)
📌 Problem Statement & Constraints
Given an integer array
nums, return the number of subarrays filled with 0. Constraints: 1 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- Every maximal run of
kconsecutive zeros contributesk * (k + 1) / 2zero-filled subarrays, since any contiguous slice of the run is valid. - So a single pass counting the current run length and accumulating it works: on a zero, increment the run and add the run length to the total.
- Adding the run length at each step is equivalent to the triangular number formula, but avoids a second pass.
- On a non-zero, reset the run to zero.
💻 Benchmark Python3 Implementation
class Solution:
def zeroFilledSubarray(self, nums: List[int]) -> int:
res = 0
run = 0
for x in nums:
if x == 0:
run += 1
res += run # run subarrays end here
else:
run = 0 # run broken
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Counting only maximal runs: you must count all subarrays within each run, which the incremental
res += rundoes. - Forgetting to reset the run: zeros separated by non-zeros would be merged into one run.
- Using the triangular formula after collecting all runs: correct but requires a second pass or extra bookkeeping.
- Confusing this with counting non-empty zero subarrays of any length: that is exactly what is being counted, so no adjustment is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.