> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Number of Submatrices That Sum to Target

> Tested Python solution for LeetCode 1074 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 1074, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Matrix](/catalog/topics/matrix), [Prefix Sum](/catalog/topics/prefix-sum). [View on LeetCode](https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1074   # by problem number
lcpy gen -s number_of_submatrices_that_sum_to_target   # by problem name
```

## Problem

Given a \<code>matrix\</code> and a \<code>target\</code>, return the number of non-empty submatrices that sum to \<code>target\</code>.

A submatrix \<code>x1, y1, x2, y2\</code> is the set of all cells \<code>matrix\[x]\[y]\</code> with \<code>x1 \<= x \<= x2\</code> and \<code>y1 \<= y \<= y2\</code>.

Two submatrices \<code>(x1, y1, x2, y2)\</code> and \<code>(x1', y1', x2', y2')\</code> are different if they have some coordinate that is different: for example, if \<code>x1 != x1'\</code>.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/09/02/mate1.jpg)

```
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.
```

```
Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
```

```
Input: matrix = [[904]], target = 0
Output: 0
```

### Constraints

* \<code>1 \<= matrix.length \<= 100\</code>
* \<code>1 \<= matrix\[0].length \<= 100\</code>
* \<code>-1000 \<= matrix\[i]\[j] \<= 1000\</code>
* \<code>-10\<sup>8\</sup> \<= target \<= 10\<sup>8\</sup>\</code>

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_submatrices_that_sum_to_target/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_submatrices_that_sum_to_target/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(rows^2 * cols)
    # Space: O(cols)
    def num_submatrix_sum_target(self, matrix: list[list[int]], target: int) -> int:
        rows, cols = len(matrix), len(matrix[0])
        count = 0
        for top in range(rows):
            col_sums = [0] * cols
            for bottom in range(top, rows):
                for c in range(cols):
                    col_sums[c] += matrix[bottom][c]
                prefix: dict[int, int] = {0: 1}
                running = 0
                for s in col_sums:
                    running += s
                    count += prefix.get(running - target, 0)
                    prefix[running] = prefix.get(running, 0) + 1
        return count
```

## Complexity

| Time | Space |
| - | - |
| O(rows^2 \* cols) | O(cols) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.