Number of Submatrices That Sum to Target — Hard Problem & Solution

Count the non-empty submatrices whose elements sum to target.

Difficulty: Hard
Topics: Arrays, Hash Table, Matrix, Prefix Sum
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Count the non-empty submatrices whose elements sum to target. A submatrix is a rectangle (x1, y1) … (x2, y2) with x1 <= x2 and y1 <= y2, and two submatrices are different whenever any of those four coordinates differ — even if the values are identical.

Example 1

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four single `0` cells.

Example 2

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

Example 3

Input: matrix = [[904]], target = 0
Output: 0

Constraints

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

How to solve Number of Submatrices That Sum to Target

Collapse two of the four degrees of freedom by fixing the column range. Row-wise prefix sums make each row's contribution O(1), and the remaining 1D problem is solved with a prefix-sum frequency map.

Approach

Precompute row prefix sums so a row's slice [c1, c2] is one subtraction.
For each column pair c1 <= c2, sweep the rows keeping a running total.
Look up running - target in a map of previously seen totals and add its count.
Record the running total, seeding the map with {0: 1} for rectangles starting at row 0.

Why it works

A rectangle is a column range plus a row range, so fixing the columns leaves exactly one contiguous range to find, and the prefix-sum map counts all of them in one pass. Seeding with {0: 1} is what lets a rectangle begin at the first row. Values can repeat and cancel, so a map of counts is required, not a set.

Complexity

Time — O(rows² · cols) — or O(cols² · rows), whichever orientation is cheaper
Space — O(rows)

Pitfalls

A set instead of a count map loses rectangles that share a prefix sum.
Forgetting the {0: 1} seed drops every rectangle anchored at the first row.
Sums reach 100 · 100 · 1000 = 10^7, so int is fine, but the running total must not be reset between column pairs without also clearing the map.

Reference solution

Python

from typing import List
from collections import defaultdict

def numSubmatrixSumTarget(matrix: List[List[int]], target: int) -> int:
    m, n = len(matrix), len(matrix[0])
    pre = [[0] * (n + 1) for _ in range(m)]
    for i in range(m):
        for j in range(n):
            pre[i][j + 1] = pre[i][j] + matrix[i][j]
    ans = 0
    for c1 in range(n):
        for c2 in range(c1, n):
            seen = defaultdict(int)
            seen[0] = 1
            total = 0
            for i in range(m):
                total += pre[i][c2 + 1] - pre[i][c1]
                ans += seen[total - target]
                seen[total] += 1
    return ans

JavaScript

var numSubmatrixSumTarget = function(matrix, target) {
    var m = matrix.length, n = matrix[0].length, i, j;
    var pre = [];
    for (i = 0; i < m; i++) {
        var row = [0];
        for (j = 0; j < n; j++) row.push(row[j] + matrix[i][j]);
        pre.push(row);
    }
    var ans = 0;
    for (var c1 = 0; c1 < n; c1++) {
        for (var c2 = c1; c2 < n; c2++) {
            var map = new Map();
            map.set(0, 1);
            var sum = 0;
            for (i = 0; i < m; i++) {
                sum += pre[i][c2 + 1] - pre[i][c1];
                var hit = map.get(sum - target);
                if (hit !== undefined) ans += hit;
                var cur = map.get(sum);
                map.set(sum, cur === undefined ? 1 : cur + 1);
            }
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue