# 3 ms Java Solution

• standard DP solution. 3 ms, beat 100 %

``````public class NumMatrix {
int [][] sum;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0)
return;
sum = new int[matrix.length+1][matrix[0].length+1];
for (int i=0; i<matrix.length; i++) {
int tmp = 0;
for (int j=0; j<matrix[0].length; j++) {
tmp += matrix[i][j];
sum[i+1][j+1] = sum[i][j+1] + tmp;
}
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
if (sum.length == 0)
return 0;
return sum[row2+1][col2+1] - sum[row2+1][col1] - sum[row1][col2+1] + sum[row1][col1];
}
}
``````

• @wangyx05 said in 3 ms Java Solution:

I have exactly the same idea as yours, however, my implementation is not as optimal as your3, but it will be much easier for everyone to understand. I will also explain the idea below with an example:
A 3*3 grids, we try to get a dp array as left

``````1 2 3      1  3  6
4 5 6  ->  5 12 21
7 8 9      12 27 45
``````

The transform formula is: dp[i][j] = dp[i-1][j] + dp[j-1][i] - dp[i-1][j-1]

Then how can we use this dp array to calculate a 2D range? The formula is (I draw a few grids to get the following formula):
res = dp[row2][col2] - dp[row1-1][col2] - dp[row2,col1-1] + dp[row1-1][col1-1]

So the implementation is as following:

``````class NumMatrix {

private int[][] dp;

public NumMatrix(int[][] matrix) {

if (null == matrix || 0 == matrix.length)
dp = new int[0][0];
else
dp = new int[matrix.length][matrix[0].length];

// build the dp array dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1](all in range)
for (int i = 0; i < dp.length; i ++)
for (int j = 0; j < dp[0].length ; j ++) {

dp[i][j] = matrix[i][j];
if (i - 1 >= 0)
dp[i][j] += dp[i - 1][j];
if (j - 1 >= 0)
dp[i][j] += dp[i][j - 1];
if (i - 1 >= 0 && j - 1 >= 0)
dp[i][j] -= dp[i - 1][j - 1];
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {

int sum = dp[row2][col2];
if (row1 - 1 >= 0)
sum -= dp[row1 - 1][col2];
if (col1 - 1 >= 0)
sum -= dp[row2][col1 - 1];

return sum += (row1 - 1 >= 0 && col1 - 1 >= 0) ? dp[row1 - 1][col1 - 1] : 0;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.