Number of Submatrices That Sum to Target Problem

Problem

Given a matrix and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

Examples

$$ \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} $$ Example 1:

1
2
3
4
5

Input:
matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output:
 4
Explanation: The four 1x1 submatrices that only contain 0.

Example 2:

1
2
3
4
5

Input:
matrix = [[1,-1],[-1,1]], target = 0
Output:
 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Example 3:

1
2
3
4

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

Solution

Method 1 – Prefix Sum + Hash Map

Intuition

Reduce the 2D submatrix sum problem to a series of 1D subarray sum problems using prefix sums and hash maps.

Approach

  1. For each pair of rows, compute the sum of elements between those rows for every column.
  2. For each such row pair, use a hash map to count the number of subarrays (columns) that sum to the target.
  3. Accumulate the count for all row pairs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size(), res = 0;
        for (int top = 0; top < m; ++top) {
            vector<int> colSum(n);
            for (int bottom = top; bottom < m; ++bottom) {
                for (int c = 0; c < n; ++c)
                    colSum[c] += matrix[bottom][c];
                unordered_map<int,int> count{{0,1}};
                int curr = 0;
                for (int v : colSum) {
                    curr += v;
                    res += count[curr - target];
                    count[curr]++;
                }
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func numSubmatrixSumTarget(matrix [][]int, target int) int {
    m, n := len(matrix), len(matrix[0])
    res := 0
    for top := 0; top < m; top++ {
        colSum := make([]int, n)
        for bottom := top; bottom < m; bottom++ {
            for c := 0; c < n; c++ {
                colSum[c] += matrix[bottom][c]
            }
            count := map[int]int{0: 1}
            curr := 0
            for _, v := range colSum {
                curr += v
                res += count[curr-target]
                count[curr]++
            }
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length, res = 0;
        for (int top = 0; top < m; ++top) {
            int[] colSum = new int[n];
            for (int bottom = top; bottom < m; ++bottom) {
                for (int c = 0; c < n; ++c)
                    colSum[c] += matrix[bottom][c];
                Map<Integer, Integer> count = new HashMap<>();
                count.put(0, 1);
                int curr = 0;
                for (int v : colSum) {
                    curr += v;
                    res += count.getOrDefault(curr - target, 0);
                    count.put(curr, count.getOrDefault(curr, 0) + 1);
                }
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun numSubmatrixSumTarget(matrix: Array<IntArray>, target: Int): Int {
        val m = matrix.size
        val n = matrix[0].size
        var res = 0
        for (top in 0 until m) {
            val colSum = IntArray(n)
            for (bottom in top until m) {
                for (c in 0 until n) colSum[c] += matrix[bottom][c]
                val count = mutableMapOf(0 to 1)
                var curr = 0
                for (v in colSum) {
                    curr += v
                    res += count.getOrDefault(curr - target, 0)
                    count[curr] = count.getOrDefault(curr, 0) + 1
                }
            }
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def numSubmatrixSumTarget(self, matrix: list[list[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        res = 0
        for top in range(m):
            colSum = [0] * n
            for bottom in range(top, m):
                for c in range(n):
                    colSum[c] += matrix[bottom][c]
                count = {0: 1}
                curr = 0
                for v in colSum:
                    curr += v
                    res += count.get(curr - target, 0)
                    count[curr] = count.get(curr, 0) + 1
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::collections::HashMap;
impl Solution {
    pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {
        let m = matrix.len();
        let n = matrix[0].len();
        let mut res = 0;
        for top in 0..m {
            let mut col_sum = vec![0; n];
            for bottom in top..m {
                for c in 0..n {
                    col_sum[c] += matrix[bottom][c];
                }
                let mut count = HashMap::new();
                count.insert(0, 1);
                let mut curr = 0;
                for &v in &col_sum {
                    curr += v;
                    res += *count.get(&(curr - target)).unwrap_or(&0);
                    *count.entry(curr).or_insert(0) += 1;
                }
            }
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    numSubmatrixSumTarget(matrix: number[][], target: number): number {
        const m = matrix.length, n = matrix[0].length;
        let res = 0;
        for (let top = 0; top < m; ++top) {
            const colSum = Array(n).fill(0);
            for (let bottom = top; bottom < m; ++bottom) {
                for (let c = 0; c < n; ++c) colSum[c] += matrix[bottom][c];
                const count = new Map<number, number>();
                count.set(0, 1);
                let curr = 0;
                for (const v of colSum) {
                    curr += v;
                    res += count.get(curr - target) ?? 0;
                    count.set(curr, (count.get(curr) ?? 0) + 1);
                }
            }
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(m^2 * n)
  • 🧺 Space complexity: O(n)