Problem

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)]

思路

• naive solution
  • loop through the coordinate of starting point and end point of a subarray
• optimization
  • thinking of the relationship between array and matrix. if we see one column in a matrix corresponding to an element in the array, then we need prefix sum for columns. because it is submatrix, we set start row and end row.
    • 
  • 时间复杂度: O(n ^ 3)
• • build prefix sum
    • 

    public int[][] submatrixSum(int[][] matrix) {
        int[][] ans = new int[2][2];
        if (matrix == null) return ans;

        int r = matrix.length;
        if (matrix.length == 0) return ans;

        int c = matrix[0].length;
        if (matrix[0].length == 0) return ans;

        int[][] sum = new int[r + 1][c + 1];
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }


        for (int x = 0; x < r; x++) {
            for (int h = x + 1; h <= r; h++) {
                Map<Integer, Integer> map = new HashMap<>();
                for (int y = 0; y <= c; y++) {
                    int area = sum[h][y] - sum[x][y];
                    if (map.containsKey(area)) {
                        ans[0][0] = x;
                        ans[0][1] = map.get(area);
                        ans[1][0] = h - 1;
                        ans[1][1] = y - 1;
                        return ans;
                    } else {
                        map.put(area, y);
                    }
                }
            }
        }
        return ans;
    }