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.
In this approach, dynamically calculate prefix sums along rows. Iterate through all pairs of rows to create a strip of the matrix and calculate the sum of each potential submatrix contained within that strip using a hash map.
The Python solution uses a double loop over possible row pairs and calculates cumulative sums for the columns between those rows. Then, using a hash map, it calculates how many segments have a certain sum value, looking to reach our target sum.
Python
JavaScript
Time Complexity: O(N^2 * M), where N is number of rows and M is number of columns.
Space Complexity: O(M) for the prefix sum array.
This approach involves examining every possible submatrix, calculating the sum, and checking if it equals the target. While not optimal, it provides a straightforward solution at the expense of efficiency.
The C++ solution uses a triple nested loop to cover all possible submatrices. It maintains an intermediate array sums to hold row-wise sums between two row indices, allowing inner loops to focus on column sums.
Time Complexity: O(N^3 * M^3), due to the multiple nested loops over possible submatrices.
Space Complexity: O(M) for the interim sums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach using Prefix Sums and HashMap | Time Complexity: O(N^2 * M), where N is number of rows and M is number of columns. |
| Brute Force Approach | Time Complexity: O(N^3 * M^3), due to the multiple nested loops over possible submatrices. |
| Default Approach | — |
| 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 |
Number of Submatrices That Sum to Target | Subarray Sum Equals K | Leetcode 1074 | Leetcode 560 • codestorywithMIK • 40,672 views views
Watch 9 more video solutions →Practice Number of Submatrices That Sum to Target with our built-in code editor and test cases.
Practice on FleetCode