Number of Submatrices That Sum to Target

Intuition

A submatrix sum is fixed by its top and bottom rows plus its left and right columns. If we first turn each column into a running vertical prefix sum, then for any chosen top row r1 and bottom row r2 the total contribution of column c across those rows becomes a single number: colPrefix[r2][c] - colPrefix[r1 - 1][c]. That collapses the two-dimensional problem for a fixed row band into a one-dimensional array where entry c is that column's band sum. The number of submatrices in this band that sum to target is exactly the number of contiguous subarrays of that 1D array summing to target, which is the classic prefix-sum-plus-hash-map count. Iterating over all O(m^2) row pairs and running the O(n) count for each gives the total.

Algorithm walkthrough

1. 1Build vertical prefix sums so colPrefix[i][c] holds the sum of column c from row 0 through row i - 1, with a leading zero row for easy differencing.
2. 2Loop over every pair of rows (top, bottom); the band sum for column c is colPrefix[bottom + 1][c] - colPrefix[top][c].
3. 3Treat these per-column band sums as a 1D array and scan it while maintaining a running sum and a hash map of prefix frequencies seeded with {0: 1}.
4. 4At each column add count[running - target] to the answer, then increment count[running], counting every subarray band that sums to target.
5. 5Accumulate across all row pairs; the final total is the number of submatrices summing to target.

Implementation

class Solution:
    def numSubmatrixSumTarget(self, matrix: list[list[int]], target: int) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        col_prefix = [[0] * cols for _ in range(rows + 1)]
        for i in range(rows):
            for c in range(cols):
                col_prefix[i + 1][c] = col_prefix[i][c] + matrix[i][c]

        answer = 0
        for top in range(rows):
            for bottom in range(top, rows):
                count = {0: 1}
                running = 0
                for c in range(cols):
                    running += col_prefix[bottom + 1][c] - col_prefix[top][c]
                    answer += count.get(running - target, 0)
                    count[running] = count.get(running, 0) + 1
        return answer