Number of submatrices that sum to target
This article is a complete analysis of 1074. Number of submatrices that sum to target from LeetCode.
Consider every possible
[a, b](top-left position) and
[c, d] (bottom-right position) pair, and check their sums.
Without loss of generality, we assume the given matrix is a square matrix with size
a, we have
n choices for
b, and we have
n choices for
a —> .
[a, b], we have
n*n pairs of
[c, d]. —>
However, each time we need to sum up all entries in the submatrix, giving us . This is unacceptable for large inputs.
Optimize the brute force strategy
Do we need to sum up all entries in a submatrix every time? Can we reuse some computations?
Observation from a simple case: if the “height” of the matrix is 1, it is essentially an array. Let
sum[i] denote the sum of the subarray from index
i. If we want to know
sum, we only need to add the third element to
sum. So we can store
sum[i], and the addition only costs .
We can extend the idea to 2D to reuse computations:
sum[i, j], we use the following loop:
Now, we can get the sum of any submatrix in use the formula, but we still have pairs of “top-left” and “bottom-right” which can’t be reduced further. The total cost is .
“Compress” rows to 1D
Number of subarrays that sum to target
It’s always easier to start with a simpler version of the problem and extend the idea.
The 1D counterpart of this problem is “number of subarrays that sum to target”.
The idea is from the discussion of 560. Subarray Sum Equals K . It is amazing how a key observation reduced the cost to .
sum[i, j] denote the sum from index
We observe that the any
sum[i, j] can be broken into two parts:
The key observation is: #occurrences of
sum[0, j]-k is equivalent to the number of subarrays that sum to
k among all possible subarrays between
j. Let’s consider an example:
From 1D to 2D
If we can control one dimension, we will reduce the matrix problem to the simpler array problem.
We first compute the prefix sum for each row, and we fix col
i an col
j to “convert” the submatrix to a subarray.
- Get prefix sum for each row —>
- For each pair of
(i, j), we need to determine the submatrices. There are pairs —>
The similar idea of manipulating the equation can also be applied to any problem associated with “find the number of sub-patterns that satisfy a given condition”.