## Monday, September 26, 2016

### Submatrix Sum

Submatrix Sum
Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.
Example
Given matrix
```[
[1 ,5 ,7],
[3 ,7 ,-8],
[4 ,-8 ,9],
]```
`return [(1,1), (2,2)`

Time: O(N^3)
Space: O(N^2)
```  public int[][] submatrixSum(int[][] matrix) {
int[][] result = new int[2][2];
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int numRows = matrix.length;
int numCols = matrix[0].length;
int[][] sum = new int[numRows + 1][numCols + 1];
// precompute sum[i][j] = sum of submatrix [(0, 0), (i, j)]
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
sum[i + 1][j + 1] = matrix[i][j] + sum[i + 1][j] + sum[i][j + 1] - sum[i][j];
}
}

Map<Integer, Integer> map = new HashMap<>();
for (int i1 = 0; i1 < numRows; i1++) {
for (int i2 = i1 + 1; i2 <= numRows; i2++) {
map.clear();
map.put(0, 0);
for (int j = 1; j <= numCols; j++) {
int diff = sum[i2][j] - sum[i1][j];
if (map.containsKey(diff)) {
result[0][0] = i1;
result[0][1] = map.get(diff);
result[1][0] = i2 - 1;
result[1][1] = j - 1;
} else {
map.put(diff, j);
}
}
}
}
return result;
}```