Solution
Approach #1 (Brute Force) [Time Limit Exceeded]
Algorithm
Each time sumRegion is called, we use a double for loop to sum all elements from .
private int[][] data; public NumMatrix(int[][] matrix) { data = matrix; } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for (int r = row1; r <= row2; r++) { for (int c = col1; c <= col2; c++) { sum += data[r][c]; } } return sum; }
Complexity analysis

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

Space complexity : . Note that
data
is a reference tomatrix
and is not a copy of it.
Approach #2 (Caching) [Memory Limit Exceeded]
Intuition
Since sumRegion could be called many times, we definitely need to do some preprocessing.
Algorithm
We could trade in extra space for speed by precalculating all possible rectangular region sum and store them in a hash table. Each sumRegion query now takes only constant time complexity.
Complexity analysis

Time complexity : time per query, time precomputation. Each sumRegion query takes time as the hash table lookup's time complexity is constant. The precomputation will take time as there are a total of possibilities need to be cached.

Space complexity : . Since there are different possibilities for both top left and bottom right points of the rectangular region, the extra space required is .
Approach #3 (Caching Rows) [Accepted]
Intuition
Remember from the 1D version where we used a cumulative sum array? Could we apply that directly to solve this 2D version?
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.
private int[][] dp; public NumMatrix(int[][] matrix) { if (matrix.length == 0  matrix[0].length == 0) return; dp = new int[matrix.length][matrix[0].length + 1]; for (int r = 0; r < matrix.length; r++) { for (int c = 0; c < matrix[0].length; c++) { dp[r][c + 1] = dp[r][c] + matrix[r][c]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { int sum = 0; for (int row = row1; row <= row2; row++) { sum += dp[row][col2 + 1]  dp[row][col1]; } return sum; }
Complexity analysis

Time complexity : time per query, time precomputation. The precomputation in the constructor takes time. The sumRegion query takes time.

Space complexity : . The algorithm uses space to store the cumulative sum of all rows.
Approach #4 (Caching Smarter) [Accepted]
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 precompute a cumulative region sum with respect to the origin at .
Sum(OD) is the cumulative region sum with respect to the origin at (0, 0).
How do we derive using the precomputed cumulative region sum?
Sum(OB) is the cumulative region sum on top of the rectangle.
Sum(OC) is the cumulative region sum to the left of the rectangle.
Sum(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 inclusionexclusion to calculate as following:
private int[][] dp; public NumMatrix(int[][] matrix) { if (matrix.length == 0  matrix[0].length == 0) return; dp = new int[matrix.length + 1][matrix[0].length + 1]; for (int r = 0; r < matrix.length; r++) { for (int c = 0; c < matrix[0].length; c++) { dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c]  dp[r][c]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return dp[row2 + 1][col2 + 1]  dp[row1][col2 + 1]  dp[row2 + 1][col1] + dp[row1][col1]; }
Complexity analysis

Time complexity : time per query, time precomputation. The precomputation in the constructor takes time. Each sumRegion query takes time.

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