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;
  }

Read full article from Submatrix Sum