Number of Submatrices That Sum to Target

Hard· 2D prefix sum· prefix sum + hash map

Problem

Count the non-empty rectangular submatrices of a grid whose elements add up to a target value. Two submatrices are different if any of their corner coordinates differ.

Examples

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

Output: 4

Only the four corner cells, each a 1x1 submatrix of 0, sum to 0.

Input: matrix = [[1,-1],[-1,1]], target = 0

Output: 5

Constraints

• 1 <= rows, cols <= 100
• -1000 <= matrix[i][j] <= 1000
• -10^8 <= target <= 10^8

Hints & approach

Hint 1

Solve the 1D version first: count subarrays with sum equal to target.

Hint 2

Fix a pair of rows (top, bottom) and collapse the band between them into one array of column sums.

Hint 3

Run the 1D prefix-sum + hash map count on each collapsed array.

Approachtry the hints first

Precompute prefix sums along each column so the sum of any vertical band of a column is O(1). For every pair of rows top <= bottom, build the array of column sums for that band, then count its subarrays summing to target using a running prefix sum and a hash map seeded with {0: 1}. Summing over all row pairs gives the total. Iterate over the smaller dimension as the outer pair to minimise work.

Time O(rows^2 * cols) · Space O(cols)

← PreviousSubarray Sums Divisible by K DoneBack to Prefix sum