LeetCode 1074: Number of Submatrices That Sum to Target

Problem Restatement

We are given an m x n matrix and an integer target.

Return the number of non-empty submatrices that sum to target.

The official constraints state that 1 <= m, n <= 100 and -1000 <= matrix[i][j] <= 1000.

Input and Output

Function shape:

def numSubmatrixSumTarget(matrix: list[list[int]], target: int) -> int:
    ...

Examples

Example 1:

matrix = [[0,1,0],[1,1,1],[0,1,0]]
target = 0

Answer:

4

Key Insight

Fix the top and bottom rows. Compress each column into a row sum between those two row boundaries. Then find how many contiguous subarrays in this compressed row sum to target — this is the classic “subarray sum equals k” problem solved with a prefix sum + hash map.

Algorithm

1. Fix row boundaries r1 and r2.
2. For each column c, compute the column sum from r1 to r2.
3. Use prefix sum + hash map to count subarrays of this column-sum array that equal target.
4. Accumulate the count.

Correctness

Every submatrix is defined by a row range [r1, r2] and a column range [c1, c2]. By fixing r1 and r2 and computing column sums, we reduce the 2D problem to a 1D subarray sum problem. The prefix sum + hash map gives O(n) per pair of rows.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Let m and n be the matrix dimensions.

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

from collections import defaultdict

class Solution:
    def numSubmatrixSumTarget(self, matrix: list[list[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        count = 0

        for r1 in range(m):
            col_sum = [0] * n
            for r2 in range(r1, m):
                for c in range(n):
                    col_sum[c] += matrix[r2][c]

                prefix = defaultdict(int)
                prefix[0] = 1
                running = 0
                for val in col_sum:
                    running += val
                    count += prefix[running - target]
                    prefix[running] += 1

        return count

Testing

def run_tests():
    s = Solution()

    assert s.numSubmatrixSumTarget([[0,1,0],[1,1,1],[0,1,0]], 0) == 4
    assert s.numSubmatrixSumTarget([[1,-1],[-1,1]], 0) == 5
    assert s.numSubmatrixSumTarget([[904]], 0) == 0

    print("all tests passed")

run_tests()