Range Sum Query 2D - Immutable Medium 0 attempts
LeetCode ↗

Range Sum Query 2D - Immutable

Medium Dynamic ProgrammingMemoization LeetCode

Given a 2D matrix, handle multiple queries to find the sum of elements inside a given rectangle.

Example: matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]], sumRegion(2,1,4,3) → 8

Sample Input
—
Sample Output
—
Constraints
  • 1 <= m, n <= 200
  • -10^4 <= matrix[i][j] <= 10^4
  • At most 10^4 calls to sumRegion
Topics
Dynamic ProgrammingMemoization

Prefix Sum 2D

class NumMatrix {
  constructor(matrix) {
    const m = matrix.length, n = matrix[0].length;
    this.prefix = Array.from({length: m+1}, () => Array(n+1).fill(0));
    for (let i = 1; i <= m; i++)
      for (let j = 1; j <= n; j++)
        this.prefix[i][j] = matrix[i-1][j-1] + this.prefix[i-1][j] + this.prefix[i][j-1] - this.prefix[i-1][j-1];
  }
  sumRegion(r1, c1, r2, c2) {
    return this.prefix[r2+1][c2+1] - this.prefix[r1][c2+1] - this.prefix[r2+1][c1] + this.prefix[r1][c1];
  }
}

Time: O(1) per query, O(mn) init | Space: O(mn)

Saved in this browser only. Private to you.

JavaScript