Number of Submatrices That Sum to Target

Hard
921.

Number of Submatrices That Sum to Target

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {number}
 */
var numSubmatrixSumTarget = function(matrix, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Number of Submatrices That Sum to Target

  1. Hint 1

    Fix the left and right columns of the rectangle. Each row then collapses to a single number.

  2. Hint 2

    The question becomes: how many contiguous runs of those row sums add to target?

  3. 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

  1. Precompute row prefix sums so a row's slice [c1, c2] is one subtraction.
  2. For each column pair c1 <= c2, sweep the rows keeping a running total.
  3. Look up running - target in a map of previously seen totals and add its count.
  4. 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

Java

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