1074. Number of Submatrices That Sum to Target #
Problem #
Given a matrix, and a target, return the number of non-empty submatrices that sum to target.
A submatrix x1, y1, x2, y2 is the set of all cells matrix[y] with x1 <= x <= x2 and y1 <= y <= y2.
Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.
Example 1:
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.
Example 2:
Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.
Note:
1 <= matrix.length <= 3001 <= matrix[0].length <= 300-1000 <= matrix[i] <= 1000-10^8 <= target <= 10^8
Problem Summary #
Given a matrix matrix and a target value target, return the number of non-empty submatrices whose sum of elements equals the target value.
A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] that satisfy x1 <= x <= x2 and y1 <= y <= y2.
If two submatrices (x1, y1, x2, y2) and (x1’, y1’, x2’, y2’) have some different coordinates (for example: x1 != x1’), then these two submatrices are also different.
Notes:
- 1 <= matrix.length <= 300
- 1 <= matrix[0].length <= 300
- -1000 <= matrix[i] <= 1000
- -10^8 <= target <= 10^8
Solution Approach #
Given a matrix, the task is to find the number of submatrices in this matrix whose sum equals target.
After reading this problem, it feels like a two-dimensional version of the sliding window. If we flatten it into a one-dimensional array, finding continuous subarrays whose sum is target becomes easy to solve. If this problem is not reduced in dimension, a pure brute-force solution is O(n^6). How can we optimize and reduce the time complexity?
This is reminiscent of Problem 1, Two Sum, where the problem of summing 2 numbers can be optimized to O(n). Here we use a similar idea: use a map to store prefix sums that have appeared in the row direction, and subtracting them gives the sum of the current row. Readers may wonder here: why can’t we store each row separately? Why must we use subtraction of prefix sums to obtain the sum of each row? Because this problem requires all solutions for submatrices. If we only store the sum of each row separately, we can only obtain smaller submatrices, and cases where larger matrices are formed by combining submatrices will be missed (of course, looping again and accumulating the submatrices would also work, but that adds another loop). For example, a submatrix may be 1*4, but stacking 2 such submatrices together forms a 2 * 4 that can also satisfy the condition. If prefix sums are not used and only the sum of each row is stored separately, a combination step is still needed in the end. With this optimization, the complexity can be optimized from O(n^6) to O(n^4), which can AC this problem, but the time complexity is still too high. How can it be optimized further?
First, a submatrix needs 4 boundaries: top, bottom, left, and right. Using 4 variables to control loops requires O(n^4), and interval accumulation over rows and columns also requires O(n^2). Interval accumulation over rows and columns can be solved with preSum. For example,
sum[i,j] = sum[j] - sum[i - 1], where sum[k] stores the cumulative sum from 0 to K: \[ \sum_{0}^{k} matrix[i]\] Then the cumulative sum within an interval can be obtained by subtracting the cumulative sum to the left of the interval’s left boundary from the interval’s right boundary (because it is a closed interval, the sum to the left of the left boundary needs to be taken). After this processing, the column dimension has been flattened.Now look at the sum in the row direction. The sum of each column can now be obtained by interval subtraction. Then this problem becomes the same as Problem 1, Two Sum. The Two Sum problem only needs O(n) time complexity to solve. Since this problem is two-dimensional, the two column boundaries still need to be looped over, so the final optimized time complexity is O(n^3). The presum can be computed directly using the original array, so the space complexity is only one O(n) dictionary.
Problems with similar ideas include Problem 560 and Problem 304.
Code #
package leetcode
func numSubmatrixSumTarget(matrix [][]int, target int) int {
m, n, res := len(matrix), len(matrix[0]), 0
for row := range matrix {
for col := 1; col < len(matrix[row]); col++ {
matrix[row][col] += matrix[row][col-1]
}
}
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
counterMap, sum := make(map[int]int, m), 0
counterMap[0] = 1 // The problem guarantees there is a solution, so initialize this to 1
for row := 0; row < m; row++ {
if i > 0 {
sum += matrix[row][j] - matrix[row][i-1]
} else {
sum += matrix[row][j]
}
res += counterMap[sum-target]
counterMap[sum]++
}
}
}
return res
}
// Brute-force solution O(n^4)
func numSubmatrixSumTarget1(matrix [][]int, target int) int {
m, n, res, sum := len(matrix), len(matrix[0]), 0, 0
for i := 0; i < n; i++ {
for j := i; j < n; j++ {
counterMap := map[int]int{}
counterMap[0] = 1 // The problem guarantees there is a solution, so initialize this to 1
sum = 0
for row := 0; row < m; row++ {
for k := i; k <= j; k++ {
sum += matrix[row][k]
}
res += counterMap[sum-target]
counterMap[sum]++
}
}
}
return res
}
// Brute-force solution, time limit exceeded! O(n^6)
func numSubmatrixSumTarget2(matrix [][]int, target int) int {
res := 0
for startx := 0; startx < len(matrix); startx++ {
for starty := 0; starty < len(matrix[startx]); starty++ {
for endx := startx; endx < len(matrix); endx++ {
for endy := starty; endy < len(matrix[startx]); endy++ {
if sumSubmatrix(matrix, startx, starty, endx, endy) == target {
//fmt.Printf("startx = %v, starty = %v, endx = %v, endy = %v\n", startx, starty, endx, endy)
res++
}
}
}
}
}
return res
}
func sumSubmatrix(matrix [][]int, startx, starty, endx, endy int) int {
sum := 0
for i := startx; i <= endx; i++ {
for j := starty; j <= endy; j++ {
sum += matrix[i][j]
}
}
return sum
}
中文