⚡Flashcard Drill➔
NeetCode #170LC-1074HardArrays & Hashing
← Back to All Problems

#170 · #1074 · Number of Submatrices That Sum to Target(元素和为目标值的子矩阵数量)

📌 Problem Statement & Constraints

Given a matrix and a target, return the number of non-empty submatrices whose sum equals target. Constraints: 1 <= m, n <= 100, -1000 <= matrix[i][j] <= 1000, -10^8 <= target <= 10^8.

💡 Core Algorithmic Approaches

  1. Fix the top row and extend the bottom row downward, maintaining a running column-sum array for the current row band.
  2. Within a fixed band, the problem reduces to the 1D version: count subarrays with sum equal to target.
  3. Solve the 1D version with prefix sums and a hash map counting how many earlier prefixes equal current - target.
  4. The total complexity is O(m^2 * n), which is 10^6 for 100x100 -- comfortably fast.

💻 Benchmark Python3 Implementation

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        res = 0
        for top in range(m):
            col = [0] * n                  # running column sums for rows [top..bottom]
            for bottom in range(top, m):
                for j in range(n):
                    col[j] += matrix[bottom][j]
                # 1D count of subarrays with sum == target
                cnt = {0: 1}               # empty prefix
                cur = 0
                for x in col:
                    cur += x
                    res += cnt.get(cur - target, 0)
                    cnt[cur] = cnt.get(cur, 0) + 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m^2 * n): for each of the O(m^2) row bands, a linear scan over the n columns. With m = n = 100 this is about 10^6 operations.
💾 Space Complexity
O(n) for the column sums and the prefix map.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting cnt = {0: 1}: submatrices starting at the top row of the band would be missed.
  • Recomputing the column sums from scratch for each band: O(m^3 * n); the incremental update as bottom grows keeps it at O(m^2 * n).
  • Trying to use a 2D prefix sum with a four-way loop: O(m^2 * n^2) = 10^8, which is too slow in Python.
  • Storing a set of prefix sums instead of counts: multiple prefixes can share a value, and each yields a distinct submatrix.
⚡
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