## DEV Community is a community of 638,993 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # Solution: Range Sum Query 2D - Immutable

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.

#### 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 matrix `matrix`.
• `int sumRegion(int row1, int col1, int row2, int col2)` Returns the sum of the elements of `matrix` 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 to `sumRegion`.

#### 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.

The sum of the rectangle (0,0)->(i,j) is equal to the cell (i,j), plus the rectangle (0,0)->(i,j-1), plus the rectangle (0,0)->(i-1,j), minus the rectangle (0,0)->(i-1,j-1). 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 out-of-bounds issues at i-1 and j-1 (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 top-left 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 doubly-subtracted top-left 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 in-place DP approach
• sumRegion: O(1)

#### Javascript Code:

(Jump to: Problem Description || Solution Idea)

``````class NumMatrix {
constructor(M) {
let ylen = M.length + 1, xlen = M.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[i-1][j-1] + this.dp[i-1][j] + this.dp[i][j-1] - this.dp[i-1][j-1]
}

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) + 1
self.dp = [ * xlen for _ in range(ylen)]
for i in range(1, ylen):
for j in range(1, xlen):
self.dp[i][j] = M[i-1][j-1] + self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1]

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.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[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}

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.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[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}

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]);
}
};
``````