Matrix block sum

Array Matrix Prefix Sum

76.4% acceptance

Feb 25, 2026

2503

400

Given a m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for: i - k <= r <= i + k, j - k <= c <= j + k, and (r, c) is a valid position in the matrix.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn matrix_block_sum(mat: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
    let m = mat.len();
    let n = mat[0].len();
    // Build 2D prefix sum
    let mut pre = vec![vec![0i32; n + 1]; m + 1];
    for i in 1..=m {
      for j in 1..=n {
        pre[i][j] = mat[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
      }
    }
    let sum = |r1: i32, c1: i32, r2: i32, c2: i32| -> i32 {
      let r1 = r1.max(0) as usize;
      let c1 = c1.max(0) as usize;
      let r2 = (r2.min(m as i32 - 1) + 1) as usize;
      let c2 = (c2.min(n as i32 - 1) + 1) as usize;
      pre[r2][c2] - pre[r1][c2] - pre[r2][c1] + pre[r1][c1]
    };
    let mut ans = vec![vec![0i32; n]; m];
    for i in 0..m {
      for j in 0..n {
        ans[i][j] = sum(i as i32 - k, j as i32 - k, i as i32 + k, j as i32 + k);
      }
    }
    ans
  }
}