Problem Statement:

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:

Let us first explore the Subarray Target Sum problem.

Given array nums we want to know number of subarrays that sum to target. Here is how we do it.

Suppose we are doing cumulative sum and at some index we have the value sum. Then we check if we have previously had any index at which the cumulative sum of sum-target was achieved. Because between those two indices the subarray sum is sum-(sum-target) or target. To check this, we use a hashmap.

 
int subarraySum(vector<int>& nums, int target) 
{
    unordered_map<int,int> H; H[0]=1;
    int sum = 0, res = 0;
    for(int num: nums)
    {
        sum += num;
        if(H.count(sum-target)) res += H[sum-target];
        H[sum]++;
    }
    return res;
}

With this method in mind, let us try to use it in our solution. The only problem is here we are dealing with 2-D. So, cumulative sum behaves differently. But what if we fix upper and lower row indices of our submatrix. Then the problem reduces to the subarray target sum problem.

 
class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) 
    {
        int m = matrix.size(), n = matrix[0].size(), res = 0;
        vector<vector<int>> matsum(m,vector<int>(n,0));
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) 
        {
            int top = (i>0) ? matsum[i-1][j] : 0;
            int left = (j>0) ? matsum[i][j-1] : 0;
            int topleft = (min(i,j)>0) ? matsum[i-1][j-1] : 0;
            matsum[i][j] = top + left - topleft + matrix[i][j];
        }
        for(int i=0; i<m; i++) for(int ii=i; ii<m; ii++)
        {
            unordered_map<int,int> H; H[0]=1;
            for(int j=0; j<n; j++)
            {
                int sum = matsum[ii][j] - ((i>0 )? matsum[i-1][j] : 0);
                if(H.count(sum-target)) res += H[sum-target];
                H[sum]++;
            }
        }
        return res;
    }
};

We can even morph it into a solution exactly like the subarray target sum problem.

 
class Solution {
public:
    int subarraySum(vector<int>& nums, int target) 
    {
        unordered_map<int,int> H; H[0]=1;
        int sum = 0, res = 0;
        for(int num: nums)
        {
            sum += num;
            if(H.count(sum-target)) res += H[sum-target];
            H[sum]++;
        }
        return res;
    }
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) 
    {
        int m = matrix.size(), n = matrix[0].size(), res = 0;
        vector<vector<int>> matsum(m,vector<int>(n,0));
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) 
            matsum[i][j] = ((i>0) ? matsum[i-1][j] : 0) + matrix[i][j];
        for(int i=0; i<m; i++) for(int ii=i; ii<m; ii++)
        {
            vector<int> A(n);
            for(int j=0; j<n; j++) A[j] = matsum[ii][j] - ((i>0) ? matsum[i-1][j] : 0);
            res += subarraySum(A, target);
        }
        return res;
    }
};

Note: The solution is based loosely on Neetcode youtube video.