749. Counting Submatrices That Hit a Target

Count the rectangular submatrices whose values add up exactly to target. Two submatrices are different when their corners differ, even if their contents match.

``` 0 1 0 1 1 1 target = 0 -> 4 0 1 0

1 -1 -1 1 target = 0 -> 5

1 2 3 4 target = 3 -> 2 ```

## Collapse two dimensions into one

Fix a PAIR of columns, c1 and c2. Every submatrix bounded by those two columns is then determined by its top and bottom row alone, and the value of each row inside that column band is a single number:

band[r] = a[r][c1] + a[r][c1+1] + ... + a[r][c2]

So the question becomes: how many contiguous stretches of band sum to target. That is exactly problem 286, solved with a prefix sum and a frequency map.

Reducing a two-dimensional count to O(C^2) runs of a one-dimensional count is the idea, and it is the standard way any "count submatrices with property X" problem is attacked once X is known for arrays.

## Row prefix sums make the band free

Precompute, for each row, its prefix sums. Then band[r] is one subtraction, so building the band for a column pair costs O(R) rather than O(R * C).

Without that the total becomes O(R C^3) and the method stops being worth it.

## The one-dimensional part, with its two traps

For each column pair:

counts = { 0: 1 } run = 0 for r in 0 .. R-1: run += band[r] total += counts[run - target] counts[run] += 1

Seed the map with one zero, or every submatrix whose top row is row 0 is lost.

Reset the map for every column pair. Carrying counts across pairs silently mixes submatrices from different column bands, which inflates the answer and is invisible on inputs where the answer happens to be large anyway.

## Why the answer can exceed the number of cells

An all-zero grid with target 0 counts EVERY submatrix, which is (R choose 2 + R) * (C choose 2 + C). On a two by two grid that is 9, not 4.

## Why collapsing the columns loses nothing

Fixing a column pair and summing each row across it is not an approximation. Every submatrix has exactly one left column and one right column, so it is counted under exactly one pair, and within that pair it is determined entirely by its top and bottom row. The outer double loop therefore partitions the submatrices rather than sampling them, and the inner sweep counts each partition completely.

That is what makes the total exact: no submatrix is visited twice and none is missed.

## Overflow

Nothing here needs 64 bits, which is worth checking rather than assuming. With R = C = 100 the number of submatrices is (R choose 2 + R) * (C choose 2 + C) = 5050 * 5050 = 25502500, about 2.5 * 10^7, so even counting every one of them stays far inside a signed 32 bit integer.

The running band sums are bounded by 100 * 100 * 10^4 = 10^8, about a twenty-first of INT_MAX, and run - target adds a target of magnitude at most 10^8 to reach 2 * 10^8 in the worst case. Both fit comfortably. The reference solutions use 64 bit types anyway, because on a grid this small it costs nothing and removes the question.

## Cost

Time O(R C^2). Space O(R C).

Constraints - `1 ≤ R, C ≤ 100` - `-10^4 ≤ each value ≤ 10^4` - `-10^8 ≤ target ≤ 10^8`