Description Link to heading

1074. Number of Submatrices That Sum to Target (Hard)

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:

  • 1 <= matrix.length <= 100
  • 1 <= matrix[0].length <= 100
  • -1000 <= matrix[i] <= 1000
  • -10^8 <= target <= 10^8

Solution Link to heading

It can be transmuted into a one-dimensional prefix sum. We may commence by enumerating the left boundary and right boundary of the rectangle. Once the left and right boundaries are firmly established, we can embark upon the solution with the perspective of a one-dimensional prefix sum. Naturally, in this context, we necessitate the antecedent computation of the one-dimensional prefix sum for each row of data. The temporal complexity ascertains itself to be $O(n^3)$.

The solution of 363. Max Sum of Rectangle No Larger Than K (Hard) is similar.

Code Link to heading 

class Solution {
  public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
        // 二维前缀和
        // 枚举左右边界，转换为一维前缀和
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> rowsum(m, vector<int>(n + 1));
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 1; j <= n; ++j) {
                rowsum[i][j] = rowsum[i][j - 1] + matrix[i][j - 1];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                // 左闭右开
                unordered_map<int, int> record;
                record[0] = 1;
                int sum = 0;
                for (int k = 1; k <= m; ++k) {
                    sum += rowsum[k - 1][j] - rowsum[k - 1][i];
                    if (record.find(sum - target) != record.end()) {
                        res += record[sum - target];
                    }
                    ++record[sum];
                }
            }
        }
        return res;
    }
};