Table of Contents

# Range Sum Query 2D – Immutable – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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]ExplanationNumMatrix 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`

`-10`

^{4}<= matrix[i][j] <= 10^{4}`0 <= row1 <= row2 < m`

`0 <= col1 <= col2 < n`

- At most
`10`

calls will be made to^{4}`sumRegion`

.

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

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

# Java Range Sum Query 2D – Immutable LeetCode Solution

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

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

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

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below