Number of Submatrices That Sum to Target: 2D Prefix Sums

Given a matrix of integers and an integer target, return the number of non-empty submatrices that sum to target. A submatrix is any contiguous rectangular region within the matrix. This is LeetCode 1074: Number of Submatrices That Sum to Target.

For example, with matrix = [[0,1,0],[1,1,1],[0,1,0]] and target = 0, the answer is 4 (four individual cells containing 0). With a larger matrix and target = 4, you need to find every rectangular subregion whose elements add up to exactly 4.

Why this problem matters

This is the 2D extension of the classic Subarray Sum Equals K problem. In one dimension, you use prefix sums and a hash map to count subarrays with a given sum in O(n) time. The challenge here is adapting that technique to two dimensions without blowing up to O(n^4) or worse.

The trick is dimensional reduction. You compress the 2D problem into many 1D problems by fixing pairs of row boundaries, then running the 1D prefix sum + hash map technique on each compressed array. This pattern of collapsing one dimension and solving the other shows up repeatedly in matrix problems, from finding the maximal sum rectangle to counting rectangles with specific properties.

Once you understand the reduction, the code is compact. The hard part is seeing that the reduction works at all, and that is what makes this a great problem for building intuition about prefix sums in higher dimensions.

The key insight

Imagine you fix two row indices, r1 and r2. For every column c, compute the sum of all elements in matrix[r1..r2][c]. This gives you a single 1D array of length n (the number of columns). Any submatrix with top row r1 and bottom row r2 corresponds to a contiguous subarray in this 1D array. So counting submatrices that sum to target between these two rows is exactly the "subarray sum equals K" problem.

To compute the column sums efficiently, you build a column prefix sum table. prefix[r][c] stores the sum of matrix[0..r-1][c]. The sum from row r1 to row r2 in column c is prefix[r2+1][c] - prefix[r1][c]. Building this table takes O(m * n) time, and looking up any vertical strip takes O(1).

Then you iterate over all O(m^2) pairs of row boundaries. For each pair, you compute the compressed 1D array in O(n) time, and run the hash map technique in O(n) time. The total is O(m^2 * n), which is about as good as it gets for this problem.

The solution

from collections import defaultdict

def numSubmatrixSumTarget(matrix, target):
    m, n = len(matrix), len(matrix[0])

    prefix = [[0] * n for _ in range(m + 1)]
    for r in range(m):
        for c in range(n):
            prefix[r + 1][c] = prefix[r][c] + matrix[r][c]

    count = 0
    for r1 in range(m):
        for r2 in range(r1, m):
            freq = defaultdict(int)
            freq[0] = 1
            running = 0
            for c in range(n):
                running += prefix[r2 + 1][c] - prefix[r1][c]
                count += freq[running - target]
                freq[running] += 1

    return count

The solution has three phases. First, build the column prefix sum table so you can compute the sum of any vertical strip in constant time. Second, iterate over all pairs of row boundaries. Third, for each pair, sweep across columns using a running sum and a frequency hash map, exactly like the 1D version.

The frequency map starts seeded with {0: 1} for each row pair. This ensures that if the running sum equals target at some column, you count the submatrix starting from column 0. After checking the map, you record the current running sum so future columns can reference it.

Visual walkthrough

Each row pair produces a 1D array. The hash map technique runs on that array to count matching subarrays. Across all row pairs, the total count gives you every submatrix that sums to the target.

Complexity analysis

Time: O(m^2 * n). There are O(m^2) row pairs. For each pair, you sweep through n columns doing O(1) work per column (hash map lookup and insertion). Building the prefix sum table is O(m * n), which is dominated by the main loop.

Space: O(m * n) for the prefix table, O(n) for the hash map. The prefix table has (m+1) rows and n columns. The hash map is cleared for each row pair and holds at most n+1 entries. If you want to reduce space, you can compute the column sums on the fly instead of precomputing the full table, but the time complexity stays the same.

You might wonder whether O(m^2 * n) can be improved. For general integer matrices (with negative numbers), this is essentially optimal. You cannot avoid iterating over all row pairs because any pair might contribute matching submatrices. Within each pair, the hash map technique is already linear.

The building blocks

1. Column prefix sum compression

The prefix sum table prefix[r][c] = sum of matrix[0..r-1][c] lets you collapse any vertical range into a single number per column. This is the same idea as 1D prefix sums but applied independently to each column. Once you have this table, the sum of elements in column c from row r1 to row r2 is prefix[r2+1][c] - prefix[r1][c].

This compression turns a 2D submatrix query into a 1D subarray query. You go from searching over four indices (r1, r2, c1, c2) to searching over three (r1, r2, and a subarray within the compressed 1D array). The hash map handles the subarray part, reducing the effective search to two indices (r1, r2).

2. Subarray sum equals K with a hash map

This is the 1D core that drives the inner loop. You maintain a running prefix sum and a frequency map. At each position, you check whether running - target exists in the map. If it does, the frequency tells you how many subarrays ending at this position sum to target. Then you record the current running sum in the map.

The key details: seed the map with {0: 1} to count subarrays that start at index 0. Check the map before updating it to avoid counting zero-length subarrays. Use a frequency count (not just first occurrence) because the same prefix sum value can appear multiple times when the array contains zeros or negative numbers.

Edge cases

• Single cell matrix. If the matrix is 1x1, return 1 if that cell equals target, otherwise 0. The algorithm handles this naturally since there is exactly one row pair and one column.
• All zeros with target = 0. Every submatrix sums to 0. The answer is the total number of non-empty submatrices: m*(m+1)/2 * n*(n+1)/2. The hash map frequency will grow rapidly as every prefix sum is 0.
• Negative values. The matrix can contain negative numbers. This is exactly why a hash map is needed instead of a sliding window. The prefix sum can decrease as you move across columns.
• Large target. If target exceeds the sum of all elements in the matrix, the answer could still be non-zero if negative numbers create subarrays that overshoot and come back. Do not short-circuit based on the total sum.
• Single row or single column. When m = 1, the outer loop runs once and the problem reduces to the standard 1D subarray sum equals K. When n = 1, each "1D array" has length 1, so you are just checking vertical strips.
• Repeated values. When many cells share the same value, the hash map may see the same prefix sum many times. The frequency count handles this correctly, each occurrence adds to the total.

From understanding to recall

The algorithm combines two patterns: column prefix sums for dimensional compression and the prefix sum + hash map trick for 1D subarray counting. Understanding why these fit together is the first step. But in an interview, you also need to remember the structure. You need to recall that you iterate over row pairs (not column pairs), that you compress columns using the prefix table, and that the hash map is reset for each row pair.

These details are easy to confuse. Should you fix rows and sweep columns, or fix columns and sweep rows? Either works, but you should pick one and drill it until the choice is automatic. The seeding of the hash map with {0: 1}, the order of check-then-update, and the O(m^2 * n) complexity are all details that slip away without practice. Spaced repetition locks them in by resurfacing the problem at the moment you are about to forget, so each review strengthens the memory instead of just refreshing it.

Related posts

• Subarray Sum Equals K - The 1D version of this problem
• Range Sum Query 2D - Immutable - 2D prefix sum fundamentals
• Maximum Subarray - Another subarray optimization using prefix thinking

CodeBricks uses spaced repetition to help you internalize patterns like the 2D prefix sum reduction. Instead of re-reading solutions, you practice writing them from scratch at increasing intervals. Each session reinforces the connection between "2D submatrix sum" and "fix row pairs, compress, run 1D hash map." Over time, the full approach becomes something you can reconstruct in minutes, not something you need to look up.