304 North Cardinal St.
Dorchester Center, MA 02124

# Range Sum Query 2D – Immutable LeetCode Solution

## Problem – Range Sum Query 2D – Immutable LeetCode Solution

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)`.

You must design an algorithm where `sumRegion` works on `O(1)` time complexity.

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)``````

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 200`
• `-104 <= matrix[i][j] <= 104`
• `0 <= row1 <= row2 < m`
• `0 <= col1 <= col2 < n`
• At most `104` calls will be made to `sumRegion`.

## Range Sum Query 2D – Immutable LeetCode Solution in C++

``````class NumMatrix {
private:
int row, col;
vector<vector<int>> sums;
public:
NumMatrix(vector<vector<int>> &matrix) {
row = matrix.size();
col = row>0 ? matrix[0].size() : 0;
sums = vector<vector<int>>(row+1, vector<int>(col+1, 0));
for(int i=1; i<=row; i++) {
for(int j=1; j<=col; j++) {
sums[i][j] = matrix[i-1][j-1] +
sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] ;
}
}
}

int sumRegion(int row1, int col1, int row2, int col2) {
return sums[row2+1][col2+1] - sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1];
}
};
``````

## Range Sum Query 2D – Immutable LeetCode Solution in Java

``````private int[][] dp;

public NumMatrix(int[][] matrix) {
if(   matrix           == null
|| matrix.length    == 0
|| matrix[0].length == 0   ){
return;
}

int m = matrix.length;
int n = matrix[0].length;

dp = new int[m + 1][n + 1];
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] -dp[i - 1][j - 1] + matrix[i - 1][j - 1] ;
}
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
int iMin = Math.min(row1, row2);
int iMax = Math.max(row1, row2);

int jMin = Math.min(col1, col2);
int jMax = Math.max(col1, col2);

return dp[iMax + 1][jMax + 1] - dp[iMax + 1][jMin] - dp[iMin][jMax + 1] + dp[iMin][jMin];
}
``````

## Range Sum Query 2D – Immutable LeetCode Solution in Python

``````class NumMatrix(object):
def __init__(self, matrix):
if matrix is None or not matrix:
return
n, m = len(matrix), len(matrix[0])
self.sums = [ [0 for j in xrange(m+1)] for i in xrange(n+1) ]
for i in xrange(1, n+1):
for j in xrange(1, m+1):
self.sums[i][j] = matrix[i-1][j-1] + self.sums[i][j-1] + self.sums[i-1][j] - self.sums[i-1][j-1]

def sumRegion(self, row1, col1, row2, col2):
row1, col1, row2, col2 = row1+1, col1+1, row2+1, col2+1
return self.sums[row2][col2] - self.sums[row2][col1-1] - self.sums[row1-1][col2] + self.sums[row1-1][col1-1]
``````
##### Range Sum Query 2D – Immutable LeetCode Solution Review:

In our experience, we suggest you solve this Range Sum Query 2D – Immutable LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Range Sum Query 2D – Immutable LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Range Sum Query 2D – Immutable LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions