⚡Flashcard Drill➔
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

  1. Every maximal run of k consecutive zeros contributes k * (k + 1) / 2 zero-filled subarrays, since any contiguous slice of the run is valid.
  2. 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.
  3. Adding the run length at each step is equivalent to the triangular number formula, but avoids a second pass.
  4. 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 += run does.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems