Watch 10 video solutions for Number of Submatrices That Sum to Target, a hard level problem involving Array, Hash Table, Matrix. This walkthrough by codestorywithMIK has 40,672 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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[x][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.
Example 3:
Input: matrix = [[904]], target = 0 Output: 0
Constraints:
1 <= matrix.length <= 1001 <= matrix[0].length <= 100-1000 <= matrix[i][j] <= 1000-10^8 <= target <= 10^8Problem Overview: You are given a 2D matrix and a target value. The task is to count how many rectangular submatrices have a sum equal to the target. Every possible submatrix must be considered, including single cells and larger rectangles.
Approach 1: Brute Force with Prefix Sum (O(m2 * n2) time, O(m * n) space)
The straightforward method enumerates every possible submatrix by selecting two rows and two columns that define its boundaries. To compute each submatrix sum efficiently, first build a 2D prefix sum matrix. This allows constant-time sum queries using inclusion–exclusion. You iterate through all top-left and bottom-right coordinate pairs and check whether the calculated sum equals the target. The method is simple to reason about and demonstrates a clear understanding of matrix prefix sums, but it becomes expensive because the number of submatrices grows quadratically with both dimensions.
Approach 2: Prefix Sums + Hash Map (O(m2 * n) time, O(n) space)
The optimized solution reduces the 2D problem into a sequence of 1D subarray problems. Fix two row boundaries (top and bottom). For each column, compute the cumulative sum of values between these rows, effectively compressing the matrix slice into a single array. Now the task becomes counting subarrays with sum equal to the target. This is solved using a running prefix sum and a hash table that stores how many times each prefix value has appeared. For each column, check whether currentSum - target exists in the map and add its frequency to the answer. This approach leverages ideas from array prefix-sum problems and dramatically cuts one dimension from the search space.
The key insight is converting the matrix rectangle sum into repeated subarray sum queries. By fixing row pairs and scanning columns once, you avoid enumerating every rectangle explicitly.
Recommended for interviews: The Prefix Sum + Hash Map approach is the expected solution. It shows that you can reduce a 2D problem to a known 1D pattern (subarray sum equals target) and apply hash-based prefix tracking. Mentioning the brute-force method first demonstrates understanding of the search space, while the optimized approach proves algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with 2D Prefix Sum | O(m^2 * n^2) | O(m * n) | Useful for understanding submatrix enumeration or when matrix size is very small |
| Row Pair Compression + Hash Map | O(m^2 * n) | O(n) | General optimal solution for large matrices and interview settings |