Increment submatrices by one

Array Matrix Prefix Sum

73.8% acceptance

Feb 25, 2026

882

You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes. You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation: Add 1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). Return the matrix mat after performing every query.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn range_add_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = n as usize;
    let mut diff = vec![vec![0i32; n + 1]; n + 1];
    for q in &queries {
      let (r1, c1, r2, c2) = (
        q[0] as usize,
        q[1] as usize,
        q[2] as usize,
        q[3] as usize,
      );
      diff[r1][c1] += 1;
      diff[r1][c2 + 1] -= 1;
      diff[r2 + 1][c1] -= 1;
      diff[r2 + 1][c2 + 1] += 1;
    }
    // Row-wise prefix sum
    for r in 0..=n {
      for c in 1..=n {
        diff[r][c] += diff[r][c - 1];
      }
    }
    // Column-wise prefix sum
    for c in 0..=n {
      for r in 1..=n {
        diff[r][c] += diff[r - 1][c];
      }
    }
    (0..n).map(|r| (0..n).map(|c| diff[r][c]).collect()).collect()
  }
}