Number of Submatrices That Sum to Target

Number of Submatrices That Sum to Target takes the famous 1-D trick — "count subarrays summing to a target with a prefix-sum hash map" — and lifts it into two dimensions. The whole problem is learning to reduce the 2-D version back down to the 1-D one you already know.

The slow way first

A submatrix is pinned down by four numbers: a top row, a bottom row, a left column, and a right column. Brute force loops over all four — that is O((rows·cols)²) rectangles, and summing each one costs even more. Far too slow.

The question to ask: can I fix part of the rectangle and turn the rest into a problem I already solved? Yes. Fix the top and bottom rows. What is left to choose is just the left and right columns — which is exactly the 1-D "count subarrays summing to target" problem.

The idea: collapse rows, then count 1-D

For every pair of rows (top, bottom), sum each column between those rows into a single number. That gives a 1-D array of column sums. A submatrix bounded by top and bottom is now just a contiguous slice of that array — so counting submatrices summing to target becomes counting subarrays summing to target, which a prefix-sum hash map does in O(n).

We accumulate column sums as bottom grows, so extending the row band by one row is just adding that new row onto the running column array — no re-summing from scratch.

Walk through it

Step through the animation. The highlighted band is the current row pair. Below it, the collapsed column sums appear, then we run a prefix-sum scan over them: seen starts as {0: 1}, and for each running prefix we ask whether prefix - target was seen before, adding its frequency to count. Each row pair contributes its share; the totals sum to 4.

Pseudocode

total = 0
for top in each row:
    col = array of zeros (one per column)
    for bottom from top down to last row:
        add row "bottom" into col, column by column
        # now count subarrays of col summing to target
        seen = {0: 1}; prefix = 0
        for s in col:
            prefix += s
            total += seen[prefix - target]   # 0 if absent
            seen[prefix] += 1
return total

The Python solution

def num_submatrices(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    total = 0
    for top in range(rows):
        col = [0] * cols
        for bottom in range(top, rows):
            for c in range(cols):
                col[c] += matrix[bottom][c]
            # count subarrays of col summing to target
            seen = {0: 1}
            prefix = 0
            for s in col:
                prefix += s
                total += seen.get(prefix - target, 0)
                seen[prefix] = seen.get(prefix, 0) + 1
    return total

• The outer two loops pick the top and bottom rows of the band.
• col holds the running column sums; each new bottom adds that row in, so building the band is incremental, not from scratch.
• The inner block is plain 1-D count subarrays == target: seen maps a prefix value to how many times it has occurred, seeded with {0: 1} so a prefix that equals target itself counts.
• Line 14 is the heart: every earlier prefix equal to prefix - target marks the start of a slice that sums to target, so we add its frequency.
• We then record the current prefix in seen for later slices.

Complexity

We pay O(cols) extra space for the column-sum array and the hash map. The speedup comes from reusing the 1-D subarray count: each of the O(rows²) row pairs is handled in a single O(cols) pass.

When this pattern shows up

Practice