1074. Number of Submatrices That Sum to Target

Given an `m x n` matrix and a target, return the number of non-empty submatrices that sum to target. Use 2D prefix-sum and hashing over columns (reduce to 1D for each pair of rows).

Input Format

2D list of ints and target int.

Output Format

Integer count.

Constraints

  • m,n ≤ 100; values ±100.

Examples

Example 1:

Input:

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

Output:

4

Explanation:

There are 4 submatrices summing to 0.

Loading...
1074. Number of Submatrices That Sum to Target