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
- Fix the top row and extend the bottom row downward, maintaining a running column-sum array for the current row band.
- Within a fixed band, the problem reduces to the 1D version: count subarrays with sum equal to
target. - Solve the 1D version with prefix sums and a hash map counting how many earlier prefixes equal
current - target. - 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
bottomgrows 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.