HardArrayHash TableMatrixPrefix Sum

Number of Submatrices That Sum to Target

1 approach, code in every language

You are given an m x n integer matrix and an integer target. Return the number of non-empty submatrices whose elements add up to exactly target.

A submatrix is defined by a contiguous range of rows (x1 to x2) and a contiguous range of columns (y1 to y2), and it includes every cell whose row is in [x1, x2] and column is in [y1, y2]. Two submatrices are counted as different if they differ in any of these four boundary indices, even if their contents are identical.

Example 1

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

Output: 4

There are four submatrices that sum to 0, each consisting of a single 0 cell at the four corners of the matrix.

Example 2

Input: matrix = [[1,-1],[-1,1]], target = 0

Output: 5

Five distinct submatrices sum to 0, including the full matrix and the four 1x2 or 2x1 bands that pair a 1 with a -1.

Constraints

1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i][j] <= 1000
-10^8 <= target <= 10^8

Column Prefix Sums plus 1D Subarray Count

Compress the matrix into per-column prefix sums, fix each pair of rows, reduce the band to a 1D array, and count subarrays summing to target with a hash map.

Loading animation…

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

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.
2Loop over every pair of rows (top, bottom); the band sum for column c is colPrefix[bottom + 1][c] - colPrefix[top][c].
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}.
4At each column add count[running - target] to the answer, then increment count[running], counting every subarray band that sums to target.
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

Time

O(m^2 * n)

Space

O(m * n)

Every pair of the m rows drives an O(n) hash-map scan; the column prefix table dominates the extra space.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free