1074. Number of Submatrices That Sum to Target

Difficulty:
Related Topics:
Similar Questions:

Problem

Given a matrix and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

  Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Example 3:

Input: matrix = [[904]], target = 0
Output: 0

  Constraints:

Solution

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {number}
 */
var numSubmatrixSumTarget = function(matrix, target) {
    var m = matrix.length;
    var n = matrix[0].length;
    for (var i = 0; i < m; i++) {
        for (var j = 1; j < n; j++) {
            matrix[i][j] += matrix[i][j - 1];
        }
    }
    var res = 0;
    for (var j1 = 0; j1 < n; j1++) {
        for (var j2 = j1; j2 < n; j2++) {
            var map = {};
            var sum = 0;
            map[0] = 1;
            for (var i = 0; i < m; i++) {
                sum += matrix[i][j2] - (matrix[i][j1 - 1] || 0);
                if (map[sum - target]) res += map[sum - target];
                map[sum] = (map[sum] || 0) + 1;
            }
        }
    }
    return res;
};

Explain:

Prefix sum and hash map.

Complexity: