# Simple java solution. O(1) time complexity. O(n*n) space complexity.

• public class NumMatrix {
int [][]array;
public NumMatrix(int[][] matrix) {
if(matrix==null||matrix.length==0||matrix[0].length==0)
return;
int m=matrix.length;
int n=matrix[0].length;
array = new int[m][n];
array[0][0]=matrix[0][0];
for(int i=1; i<m; i++)
{
array[i][0]=array[i-1][0]+matrix[i][0];
}
for(int j=1; j<n; j++)
{
array[0][j]=array[0][j-1]+matrix[0][j];
}

``````    for(int i=1; i<m; i++)
{
for(int j=1; j<n; j++)
{
array[i][j]=array[i-1][j]+array[i][j-1]-array[i-1][j-1]+matrix[i][j];
}
}

}

public int sumRegion(int row1, int col1, int row2, int col2) {
if(array==null)
return 0;
if(row1==0&&col1==0)
return array[row2][col2];
if(row1==0)
return array[row2][col2]-array[row2][col1-1];
if(col1==0)
return array[row2][col2]-array[row1-1][col2];

return array[row2][col2]-array[row1-1][col2]-array[row2][col1-1]+array[row1-1][col1-1];

}
``````

}

• Dude...you have two for loops...how can it be O(1) time...

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