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

Range Sum Query 2D - Immutable

Medium Dynamic ProgrammingMemoization LeetCode

You're given a fixed 2D matrix, and you need to answer many queries asking for the sum of all elements inside a given rectangular region.

Input Format
Implement the class NumMatrix. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 ยท Run Sample

Input
constructorArgs = [[[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]]]
operations = [["sumRegion",2,1,4,3],["sumRegion",1,1,2,2],["sumRegion",1,2,2,4]]
Output
[8,11,12]

Example 2

Input
constructorArgs = [[[5]]]
operations = [["sumRegion",0,0,0,0]]
Output
[5]
Constraints
  • 1 <= m, n <= 200
  • -10^4 <= matrix[i][j] <= 10^4
  • At most 10^4 calls to sumRegion
Test Cases (2)
Case 1
Args: [[[[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],["sumRegion",1,1,2,2],["sumRegion",1,2,2,4]]] Expected: [8,11,12]
Case 2
Args: [[[[5]]],[["sumRegion",0,0,0,0]]] Expected: [5]
Topics
Dynamic ProgrammingMemoization

Prefix Sum 2D

javascript
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