Number of Submatrices That Sum to Target
leetcode 1074. Number of Submatrices That Sum to Target
Intuition
Prerequisite: 560. Subarray Sum Equals K
For each row, calculate the prefix sum.
For each pair of columns, calculate the accumulated sum of rows.
Use things that you learned from 560. Subarray Sum Equals K, Perform a O(n^2 * nlog(n)) search.
Code
cpp
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
// linear time: construct a matrix with sum of 0,0 to i,j
// constant time access sum of a sub-matrix a,b to i,j is i.j - a.j - i.b
vector<vector<int>> dp(matrix);
for (int i = 0; i < matrix.size(); i++) {
for (int j = 1; j < matrix[0].size(); j++) {
dp[i][j] += dp[i][j-1];
}
}
int res = 0;
unordered_map<int,int>mp;
// careful about how we loop through matrix
for (int a = 0; a < matrix[0].size(); a++) {
for (int i = a; i < matrix[0].size(); i++) {
mp = {{0,1}}; // clear map
int cnt = 0;
for (int j = 0; j < matrix.size(); j++) {
cnt += dp[j][i] - (a > 0 ? dp[j][a-1] : 0);
int t = cnt - target;
if(mp.find(t) != end(mp))
res += mp[t];
mp[cnt]++;
}
}
}
return res;
}Complexity Analysis
Time: O((n^3) * log(n))
Space: O(n)
Blazingly Fast Solution
Runtime: 299 ms, faster than 99.48%
Memory Usage: 9.1 MB, less than 94.64%
WARNING
But it looks like an O(n^4) solution
cpp
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size(), sums[100], res = 0;
for(int i1 = 0; i1 < m; i1++) {
memset(sums, 0, sizeof(sums));
for(int i2 = i1; i2 < m; i2++) {
for (int j = 0; j < n; j++)
sums[j] += matrix[i2][j];
for (int j = 0; j < n; j++) {
int sum = 0;
for(int k = j; k < n; k++)
res += (target == (sum += sums[k]));
}
}
}
return res;
}