# My sometimes naive solution with two hash

• performance: estimated O((mn/c)^2), where c is const determined by local factor

First, I flatten the 2D array into f(row, col) = row*column length + col.
Then use two hash map to hold the already computed 2D sum.

H <f(row1, col1), H<f(row2, col2) -> sum>>

``````public class NumMatrix {
private int[][] pre;
private HashMap<Integer, HashMap<Integer,Integer>> visited = new HashMap<>();
private int len;
public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return;
//throw new IllegalArgumentException("Input matrix Err");
this.len = matrix[0].length;
this.pre = new int[matrix.length][matrix[0].length+1];
for (int i = 0; i < matrix.length; i++) {
for (int j = 1; j <= matrix[i].length; j++) {
pre[i][j] = pre[i][j-1] + matrix[i][j-1];
}
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
int offset1 = row1*this.len + col1;
int offset2 = row2*this.len + col2;
if (this.visited.containsKey(offset1)
&& this.visited.get(offset1).containsKey(offset2))
return this.visited.get(offset1).get(offset2);

visited.put(offset1, new HashMap<>());
int sum = 0;
for (int i = row1; i <= row2; i++) {
sum += this.pre[i][col2+1] - this.pre[i][col1];
}
visited.get(offset1).put(offset2, sum);

return sum;
}
}
``````

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