DIY: Range Sum Query 2D — Immutable
Solve the interview question "Range Sum Query 2D — Immutable" in this lesson.
We'll cover the following
Problem statement
Given an m * n
matrix, you need to handle multiple queries of the following type:
Calculate the sum of the elements of the matrix inside the rectangle defined by its upper left corner, $(row1, col1)$, and lower right corner, $(row2, col2)$.
Constraints
You can assume the following constraints for this problem:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
105 <= matrix[i][j] <= 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
Input
The NumMatrix
class constructor takes the matrix
as the input. The sumRegion()
function takes the four integer inputs that represent the starting and ending coordinates of the subregion. Here is an example of the consecutive inputs to the sumRegion()
function:
numMatrix = NumMatrix(
[
[1, 3, 5],
[2, 4, 6],
[7, 8, 2],
[9, 3, 6]
])
// Example  1
numMatrix.sumRegion(0, 0, 2, 2)
// Example  2
numMatrix.sumRegion(0, 1, 3, 2)
// Example  3
numMatrix.sumRegion(2, 1, 3, 1)
Output
The output of the sumRegion()
function is an integer that represents the region’s sum. Here is an example of the output:
// Example  1
38
// Example  2
37
// Example  3
11
Coding exercise
You need to implement the NumMatrix
class, whose skeleton is provided in the code playground below. You will need to implement the following methods:

NumMatrix(int[][] matrix)
: This method initializes the object with the integer matrix,matrix
. 
int sumRegion(int row1, int col1, int row2, int col2)
: This method returns the sum of the elements of the matrix inside the rectangle defined by its upper left corner, $(row1, col1)$, and lower right corner, $(row2, col2)$.
Level up your interview prep. Join Educative to access 70+ handson prep courses.