Submatrix Sum

Submatrix Sum

13%

Accepted

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.

Have you met this question in a real interview? 

Yes

Example

Given matrix

[
  [1 ,5 ,7],
  [3 ,7 ,-8],
  [4 ,-8 ,9],
]

return [(1,1), (2,2)]

Challenge

O(n3) time.

public class Solution {
    /**
     * @param matrix an integer matrix
     * @return the coordinate of the left-up and right-down number
     */
    public int[][] submatrixSum(int[][] matrix) {
        // Write your code here
        int m = matrix.length, n = matrix[0].length;
       
        int[][] res = new int[2][2];
       
        for(int i = 0; i < n; i++){
            int[] sum = new int[m];
            for(int j = i; j < n; j++){
               
                for(int k = 0; k < m; k++){
                    sum[k] += matrix[k][j];
                }
               
                HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
                int lastSum = 0;
                map.put(0, -1); // important
                for(int l = 0; l < m; l++){
                    lastSum += sum[l];
                    if(map.containsKey(lastSum)){
                       
                        res = new int[][] {{map.get(lastSum)+1, i}, {l, j}};
                        return res;
                    }
                    map.put(lastSum, l);
                }
            }
        }
        return res;
    }
}