Algorithm
Problem Name: 1074. Number of Submatrices That Sum to Target
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 <= 1001 <= matrix[0].length <= 100-1000 <= matrix[i] <= 1000-10^8 <= target <= 10^8
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int[][] prefixSum = new int[rows + 1][cols + 1];
for (int i = 1; i < = rows; i++) {
for (int j = 1; j < = cols; j++) {
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
int count = 0;
int currSum = 0;
for (int i = 1; i < = rows; i++) {
for (int j = i; j < = rows; j++) {
Map map = new HashMap<>();
map.put(0, 1);
for (int k = 1; k < = cols; k++) {
currSum = prefixSum[j][k] - prefixSum[i - 1][k];
count += map.getOrDefault(currSum - target, 0);
map.put(currSum, map.getOrDefault(currSum, 0) + 1);
}
}
}
return count;
}
}
Input
matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output
4
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numSubmatrixSumTarget = function(matrix, target) {
let a = matrix
let n = a.length, m = a[0].length;
const cum = Array.from({length: n + 1}, () => new Array(m + 1).fill(0));
for(let i = 0;i < n;i++){
for(let j = 0;j < m;j++){
cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + a[i][j];
}
}
let ans = 0;
for(let i = 0;i < n;i++){
for(let j = i;j < n;j++){
let map = new Map();
for(let k = 0;k < = m;k++){
let v = cum[j+1][k] - cum[i][k];
if(map.has(v - target)){
ans += map.get(v-target);
}
if(map.has(v)){
map.set(v, map.get(v)+1);
}else{
map.set(v, 1);
}
}
}
}
return ans;
};
Input
matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output
4
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
m, n = len(matrix), len(matrix[0])
for row in matrix:
for i in range(1, n):
row[i] += row[i-1]
res = 0
for i in range(n):
for j in range(i, n):
c = {0:1}
cur = 0
for row in matrix:
cur += row[j] - (row[i-1] if i else 0)
if cur - target in c:
res += c[cur-target]
c[cur] = c.get(cur, 0) + 1
return res
Input
matrix = [[1,-1],[-1,1]], target = 0
Output
5