## 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 <= 100`
• `1 <= 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;
}
}
``````
Copy The Code &

Input

cmd
matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

Output

cmd
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;
};
``````
Copy The Code &

Input

cmd
matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

Output

cmd
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
``````
Copy The Code &

Input

cmd
matrix = [[1,-1],[-1,1]], target = 0

Output

cmd
5