# LeetCode 1074: Number of Submatrices That Sum to Target

## Problem Restatement

We are given an `m x n` matrix and an integer `target`.

Return the number of non-empty submatrices that sum to `target`.

The official constraints state that `1 <= m, n <= 100` and `-1000 <= matrix[i][j] <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Matrix and integer `target` |
| Output | Number of submatrices summing to `target` |

Function shape:

```python
def numSubmatrixSumTarget(matrix: list[list[int]], target: int) -> int:
    ...
```

## Examples

Example 1:

```python
matrix = [[0,1,0],[1,1,1],[0,1,0]]
target = 0
```

Answer:

```python
4
```

## Key Insight

Fix the top and bottom rows. Compress each column into a row sum between those two row boundaries. Then find how many contiguous subarrays in this compressed row sum to `target` — this is the classic "subarray sum equals k" problem solved with a prefix sum + hash map.

## Algorithm

1. Fix row boundaries `r1` and `r2`.
2. For each column `c`, compute the column sum from `r1` to `r2`.
3. Use prefix sum + hash map to count subarrays of this column-sum array that equal `target`.
4. Accumulate the count.

## Correctness

Every submatrix is defined by a row range `[r1, r2]` and a column range `[c1, c2]`. By fixing `r1` and `r2` and computing column sums, we reduce the 2D problem to a 1D subarray sum problem. The prefix sum + hash map gives O(n) per pair of rows.

## Edge Cases

- Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
- Confirm the iteration order matches the recurrence dependencies.
- For optimization DP, separate impossible states from valid states with value `0`.

## Complexity

Let `m` and `n` be the matrix dimensions.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m^2 * n)` | `O(m^2)` row pairs, each taking `O(n)` |
| Space | `O(m + n)` | Column sums and prefix hash map |

## Common Pitfalls

- Do not overwrite a state before all transitions that still need the old value have used it.
- Use the problem constraints to choose between full tables and compressed state.

## Implementation

```python
from collections import defaultdict

class Solution:
    def numSubmatrixSumTarget(self, matrix: list[list[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        count = 0

        for r1 in range(m):
            col_sum = [0] * n
            for r2 in range(r1, m):
                for c in range(n):
                    col_sum[c] += matrix[r2][c]

                prefix = defaultdict(int)
                prefix[0] = 1
                running = 0
                for val in col_sum:
                    running += val
                    count += prefix[running - target]
                    prefix[running] += 1

        return count
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numSubmatrixSumTarget([[0,1,0],[1,1,1],[0,1,0]], 0) == 4
    assert s.numSubmatrixSumTarget([[1,-1],[-1,1]], 0) == 5
    assert s.numSubmatrixSumTarget([[904]], 0) == 0

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Cross matrix, target 0 | `4` | Four submatrices sum to zero |
| Alternating signs | `5` | Many zero-sum submatrices |
| Single non-zero cell | `0` | No zero-sum submatrix |