Number of Submatrices That Sum to Target — Solution
Number of Submatrices That Sum to Target solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Submatrices That Sum to Target is a hard coding problem on arrays, hash table and matrix, asked in Amazon, Google and Meta interviews.
- 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 <= 1001 <= matrix[0].length <= 100-1000 <= matrix[i][j] <= 1000-10^8 <= target <= 10^8
Hints for Number of Submatrices That Sum to Target
Hint 1
Fix the left and right columns of the rectangle. Each row then collapses to a single number.
Hint 2
The question becomes: how many contiguous runs of those row sums add to
target?Hint 3
That is the classic "subarray sum equals k" counted with a hash map of prefix sums.
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 - targetin 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, sointis 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 ansJava
public static int numSubmatrixSumTarget(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int[][] pre = new int[m][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) pre[i][j + 1] = pre[i][j] + matrix[i][j];
}
int ans = 0;
for (int c1 = 0; c1 < n; c1++) {
for (int c2 = c1; c2 < n; c2++) {
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1);
int sum = 0;
for (int i = 0; i < m; i++) {
sum += pre[i][c2 + 1] - pre[i][c1];
ans += seen.getOrDefault(sum - target, 0);
seen.merge(sum, 1, Integer::sum);
}
}
}
return ans;
}C++
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int m = (int) matrix.size(), n = (int) matrix[0].size();
vector<vector<int>> pre(m, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) pre[i][j + 1] = pre[i][j] + matrix[i][j];
}
int ans = 0;
for (int c1 = 0; c1 < n; c1++) {
for (int c2 = c1; c2 < n; c2++) {
unordered_map<int, int> seen;
seen[0] = 1;
int sum = 0;
for (int i = 0; i < m; i++) {
sum += pre[i][c2 + 1] - pre[i][c1];
auto it = seen.find(sum - target);
if (it != seen.end()) ans += it->second;
seen[sum]++;
}
}
}
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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets