Number of submatrices that sum to target

Array Hash Table Matrix Prefix Sum

74.6% acceptance

Feb 25, 2026

3895

107

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

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_submatrix_sum_target(matrix: Vec<Vec<i32>>, target: i32) -> i32 {
    let (m, n) = (matrix.len(), matrix[0].len());
    let mut ans = 0;
    for r1 in 0..m {
      let mut col_sum = vec![0i32; n];
      for r2 in r1..m {
        for c in 0..n { col_sum[c] += matrix[r2][c]; }
        let mut prefix_count: std::collections::HashMap<i32, i32> = std::collections::HashMap::new();
        prefix_count.insert(0, 1);
        let mut prefix = 0i32;
        for &v in &col_sum {
          prefix += v;
          ans += prefix_count.get(&(prefix - target)).copied().unwrap_or(0);
          *prefix_count.entry(prefix).or_insert(0) += 1;
        }
      }
    }
    ans
  }
}