This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given a 2D matrix *matrix*, find the sum of the elements inside the rectangle defined by its upper left corner (*row*1, *col*1) and lower right corner (*row*2, *col*2).

The above rectangle (with the red border) is defined by (row1, col1) = **(2, 1)** and (row2, col2) = **(4, 3)**, which contains sum = **8**.

**Example:**

Given matrix = [ [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] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12

**Note:**

- You may assume that the matrix does not change.
- There are many calls to
*sumRegion*function. - You may assume that
*row*1 ≤*row*2 and*col*1 ≤*col*2.

b'

\n## Solution

\n

\n#### Approach #1 (Brute Force) [Time Limit Exceeded]

\n\n

\n#### Approach #2 (Caching) [Memory Limit Exceeded]

\n

\n#### Approach #3 (Caching Rows) [Accepted]

\n\n

\n#### Approach #4 (Caching Smarter) [Accepted]

\n\n

'
\n\n

\n\n

**Algorithm**

Each time *sumRegion* is called, we use a double for loop to sum all elements from .

private int[][] data;\n\npublic NumMatrix(int[][] matrix) {\n data = matrix;\n}\n\npublic int sumRegion(int row1, int col1, int row2, int col2) {\n int sum = 0;\n for (int r = row1; r <= row2; r++) {\n for (int c = col1; c <= col2; c++) {\n sum += data[r][c];\n }\n }\n return sum;\n}\n

**Complexity analysis**

- \n
- \n
Time complexity : time per query.\nAssume that and represents the number of rows and columns respectively, each

\n*sumRegion*query can go through at most elements. \n - \n
Space complexity : . Note that

\n`data`

is a*reference*to`matrix`

and is not a copy of it. \n

\n

**Intuition**

Since *sumRegion* could be called many times, we definitely need to do some pre-processing.

**Algorithm**

We could trade in extra space for speed by pre-calculating all possible rectangular region sum and store them in a hash table. Each *sumRegion* query now takes only constant time complexity.

**Complexity analysis**

- \n
- \n
Time complexity : time per query, time pre-computation.\nEach

\n*sumRegion*query takes time as the hash table lookup\'s time complexity is constant. The pre-computation will take time as there are a total of possibilities need to be cached. \n - \n
Space complexity : .\nSince there are different possibilities for both top left and bottom right points of the rectangular region, the extra space required is .

\n \n

\n

**Intuition**

Remember from the 1D version where we used a cumulative sum array? Could we apply that directly to solve this 2D version?

\n**Algorithm**

Try to see the 2D matrix as rows of 1D arrays. To find the region sum, we just accumulate the sum in the region row by row.

\nprivate int[][] dp;\n\npublic NumMatrix(int[][] matrix) {\n if (matrix.length == 0 || matrix[0].length == 0) return;\n dp = new int[matrix.length][matrix[0].length + 1];\n for (int r = 0; r < matrix.length; r++) {\n for (int c = 0; c < matrix[0].length; c++) {\n dp[r][c + 1] = dp[r][c] + matrix[r][c];\n }\n }\n}\n\npublic int sumRegion(int row1, int col1, int row2, int col2) {\n int sum = 0;\n for (int row = row1; row <= row2; row++) {\n sum += dp[row][col2 + 1] - dp[row][col1];\n }\n return sum;\n}\n

**Complexity analysis**

- \n
- \n
Time complexity : time per query, time pre-computation.\nThe pre-computation in the constructor takes time. The

\n*sumRegion*query takes time. \n - \n
Space complexity : .\nThe algorithm uses space to store the cumulative sum of all rows.

\n \n

\n

**Algorithm**

We used a cumulative sum array in the 1D version. We notice that the cumulative sum is computed with respect to the origin at index 0. Extending this analogy to the 2D case, we could pre-compute a cumulative region sum with respect to the origin at .

\n

\nSum(OD) is the cumulative region sum with respect to the origin at (0, 0).

How do we derive using the pre-computed cumulative region sum?

\n

\nSum(OB) is the cumulative region sum on top of the rectangle.

\nSum(OC) is the cumulative region sum to the left of the rectangle.

\nSum(OA) is the cumulative region sum to the top left corner of the rectangle.

Note that the region is covered twice by both and . We could use the principle of inclusion-exclusion to calculate as following:

\n\n\n

\nprivate int[][] dp;\n\npublic NumMatrix(int[][] matrix) {\n if (matrix.length == 0 || matrix[0].length == 0) return;\n dp = new int[matrix.length + 1][matrix[0].length + 1];\n for (int r = 0; r < matrix.length; r++) {\n for (int c = 0; c < matrix[0].length; c++) {\n dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];\n }\n }\n}\n\npublic int sumRegion(int row1, int col1, int row2, int col2) {\n return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];\n}\n

**Complexity analysis**

- \n
- \n
Time complexity : time per query, time pre-computation.\nThe pre-computation in the constructor takes time. Each

\n*sumRegion*query takes time. \n - \n
Space complexity : .\nThe algorithm uses space to store the cumulative region sum.

\n \n