## 304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). 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:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

b'
\n\n

## Solution

\n
\n

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

\n

Algorithm

\n

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

\n
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
\n

Complexity analysis

\n
\n
• \n

Time complexity : time per query.\nAssume that and represents the number of rows and columns respectively, each sumRegion query can go through at most elements.

\n
• \n
• \n

Space complexity : . Note that data is a reference to matrix and is not a copy of it.

\n
• \n
\n
\n

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

\n

Intuition

\n

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

\n

Algorithm

\n

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.

\n

Complexity analysis

\n
\n
• \n

Time complexity : time per query, time pre-computation.\nEach 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
• \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
\n

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

\n

Intuition

\n

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

\n

Algorithm

\n

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.

\n
private int[][] dp;\n\npublic NumMatrix(int[][] matrix) {\n    if (matrix.length == 0 || matrix.length == 0) return;\n    dp = new int[matrix.length][matrix.length + 1];\n    for (int r = 0; r < matrix.length; r++) {\n        for (int c = 0; c < matrix.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
\n

Complexity analysis

\n
\n
• \n

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

\n
• \n
• \n

Space complexity : .\nThe algorithm uses space to store the cumulative sum of all rows.

\n
• \n
\n
\n

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

\n

Algorithm

\n

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

\n

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

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

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

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

\n

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

\n
private int[][] dp;\n\npublic NumMatrix(int[][] matrix) {\n    if (matrix.length == 0 || matrix.length == 0) return;\n    dp = new int[matrix.length + 1][matrix.length + 1];\n    for (int r = 0; r < matrix.length; r++) {\n        for (int c = 0; c < matrix.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
\n

Complexity analysis

\n
\n
• \n

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

\n
• \n
• \n

Space complexity : .\nThe algorithm uses space to store the cumulative region sum.

\n
• \n
\n
'