# Time limit exceeding on the most efficient approach :(

• My code is exceeding the time limit, even though, on referring to the editorial solution, I found that my implementation is the most efficient one (that involving caching region sums i.e. Approach #4 (Caching Smarter))

Could someone please review what could be going wrong. The time complexity of the pre-computation step is O(mn) and space complexity is O(mn) too. All queries take O(1) time.

``````public class NumMatrix {
int sum[][] = null;
public NumMatrix(int[][] matrix) {
if(matrix.length > 0){
int rows = matrix.length;
int cols = matrix[0].length;
sum = new int[rows][cols];
sum[0][0] = matrix[0][0];
for(int col = 1; col < cols ; col++ ){
sum[0][col] = sum[0][col-1] + matrix[0][col];
}
for(int row = 1; row < rows ; row++ ){
sum[row][0] = sum[row-1][0] + matrix[row][0];
}

for(int row = 1; row < rows ; row++ )
for(int col = 1; col < cols ; col++ ){
sum[row][col] = sum[row-1][col] + sum[row][col-1] - sum[row-1][col-1] + matrix[row][col];
}
}

}

public int sumRegion(int row1, int col1, int row2, int col2) {
if(sum == null){
return 0;
}
int prev = 0;
int x = 0;
int y = 0;
if(row1 > 0 && col1 > 0){
prev = sum[row1-1][col1-1];
}
x = (row1 > 0) ? sum[row1-1][col2]: 0;
y = (col1 > 0) ? sum[row2][col1-1]: 0;
return sum[row2][col2] - (x + y - prev);
}
}

// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);``````

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