This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #304 (Medium): Range Sum Query 2D  Immutable
Description:
(Jump to: Solution Idea  Code: JavaScript  Python  Java  C++)
Given a 2D matrix
matrix
, handle multiple queries of the following type:
 Calculate the sum of the elements of
matrix
inside the rectangle defined by its upper left corner(row1, col1)
and lower right corner(row2, col2)
.Implement the
NumMatrix
class:
NumMatrix(int[][] matrix)
Initializes the object with the integer matrixmatrix
.int sumRegion(int row1, int col1, int row2, int col2)
Returns the sum of the elements ofmatrix
inside the rectangle defined by its upper left corner(row1, col1)
and lower right corner(row2, col2)
.
Examples:
Example 1: Input: ["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]Output: [null, 8, 11, 12] Explanation: NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)Visual:
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
10^5 <= matrix[i][j] <= 10^5
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
 At most
10^4
calls will be made tosumRegion
.
Idea:
(Jump to: Problem Description  Code: JavaScript  Python  Java  C++)
This problem brings up one of the characteristics of a 2D matrix: the sum of the elements in any rectangular range of a matrix (M) can be defined mathematically by the overlap of four other rectangular ranges that originate at M[0][0].
The sum of the rectangle (0,0)>(i,j) is equal to the cell (i,j), plus the rectangle (0,0)>(i,j1), plus the rectangle (0,0)>(i1,j), minus the rectangle (0,0)>(i1,j1). We subtract the last rectangle because it represents the overlap of the previous two rectangles that were added.
With this information, we can use a dynamic programming (DP) approach to build a prefix sum matrix (dp) from M iteratively, where dp[i][j] will represent the sum of the rectangle (0,0)>(i,j). We'll add an extra row and column in order to prevent outofbounds issues at i1 and j1 (similar to a prefix sum array), and we'll fill dp with 0s.
At each cell, we'll add its value from M to the dp values of the cell on the left and the one above, which represent their respective rectangle sums, and then subtract from that the topleft diagonal value, which represents the overlapping rectangle of the previous two additions.
Then, we just reverse the process for sumRegion(): We start with the sum at dp[R2+1][C2+1] (due to the added row/column), then subtract the left and top rectangles before adding back in the doublysubtracted topleft diagonal rectangle.
(Note: Even though the test cases will pass when using an int matrix for dp, the values of dp can range from 4e9 to 4e9 per the listed constraints, so we should use a data type capable of handling more than 32 bits.)

Time Complexity:
 constructor: O(M * N) where M and N are the dimensions of the input matrix
 sumRegion: O(1)

Space Complexity:
 constructor: O(M * N) for the DP matrix
 constructor: O(1) if you're able to modify the input and use an inplace DP approach
 sumRegion: O(1)
Javascript Code:
(Jump to: Problem Description  Solution Idea)
class NumMatrix {
constructor(M) {
let ylen = M.length + 1, xlen = M[0].length + 1
this.dp = Array.from({length: ylen}, () => new Array(xlen).fill(0))
for (let i = 1; i < ylen; i++)
for (let j = 1; j < xlen; j++)
this.dp[i][j] = M[i1][j1] + this.dp[i1][j] + this.dp[i][j1]  this.dp[i1][j1]
}
sumRegion(R1, C1, R2, C2) {
return this.dp[R2+1][C2+1]  this.dp[R2+1][C1]  this.dp[R1][C2+1] + this.dp[R1][C1]
}
};
Python Code:
(Jump to: Problem Description  Solution Idea)
class NumMatrix:
def __init__(self, M: List[List[int]]):
ylen, xlen = len(M) + 1, len(M[0]) + 1
self.dp = [[0] * xlen for _ in range(ylen)]
for i in range(1, ylen):
for j in range(1, xlen):
self.dp[i][j] = M[i1][j1] + self.dp[i1][j] + self.dp[i][j1]  self.dp[i1][j1]
def sumRegion(self, R1: int, C1: int, R2: int, C2: int) > int:
return self.dp[R2+1][C2+1]  self.dp[R2+1][C1]  self.dp[R1][C2+1] + self.dp[R1][C1]
Java Code:
(Jump to: Problem Description  Solution Idea)
class NumMatrix {
long[][] dp;
public NumMatrix(int[][] M) {
int ylen = M.length + 1, xlen = M[0].length + 1;
dp = new long[ylen][xlen];
for (int i = 1; i < ylen; i++)
for (int j = 1; j < xlen; j++)
dp[i][j] = M[i1][j1] + dp[i1][j] + dp[i][j1]  dp[i1][j1];
}
public int sumRegion(int R1, int C1, int R2, int C2) {
return (int)(dp[R2+1][C2+1]  dp[R2+1][C1]  dp[R1][C2+1] + dp[R1][C1]);
}
}
C++ Code:
(Jump to: Problem Description  Solution Idea)
class NumMatrix {
vector<vector<long>> dp;
public:
NumMatrix(vector<vector<int>>& M) {
int ylen = M.size() + 1, xlen = M[0].size() + 1;
dp = vector<vector<long>>(ylen, vector<long>(xlen, 0));
for (int i = 1; i < ylen; i++)
for (int j = 1; j < xlen; j++)
dp[i][j] = M[i1][j1] + dp[i1][j] + dp[i][j1]  dp[i1][j1];
}
int sumRegion(int R1, int C1, int R2, int C2) {
return (int)(dp[R2+1][C2+1]  dp[R2+1][C1]  dp[R1][C2+1] + dp[R1][C1]);
}
};
Discussion (0)