Number of Submatrices That Sum to Target
HardPrompt
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^8
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by pre-calculating a 2D prefix sum matrix. This allows us to find the sum of any submatrix in constant time, reducing the overall complexity.
Algorithm
- Create a 2D prefix sum matrix
prefixSumof size(rows+1) x (cols+1). - Populate
prefixSumin O(R * C) time. - Initialize a counter
countto 0. - Iterate through all possible top-left
(r1, c1)and bottom-right(r2, c2)corners of submatrices. - For each submatrix, calculate its sum in O(1) using the
prefixSummatrix. - If the sum equals
target, incrementcount. - Return
count.
Walkthrough
First, we create a prefixSum matrix of size (rows + 1) x (cols + 1). prefixSum[i][j] will store the sum of the rectangle from (0, 0) to (i-1, j-1). This prefixSum matrix can be computed in O(R * C) time using the formula: prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]. After the prefixSum matrix is built, we iterate through all possible submatrices using four nested loops, just like in the brute-force approach. However, instead of calculating the sum with two extra loops, we use the prefixSum matrix to get the sum in O(1) time. The sum of the submatrix from (r1, c1) to (r2, c2) is given by prefixSum[r2+1][c2+1] - prefixSum[r1][c2+1] - prefixSum[r2+1][c1] + prefixSum[r1][c1]. If this sum equals the target, we increment our count.
class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { int rows = matrix.length; int cols = matrix[0].length; int count = 0; // Create and compute the 2D prefix sum matrix int[][] prefixSum = new int[rows + 1][cols + 1]; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]; } } // Iterate over all possible submatrices for (int r1 = 1; r1 <= rows; r1++) { for (int c1 = 1; c1 <= cols; c1++) { for (int r2 = r1; r2 <= rows; r2++) { for (int c2 = c1; c2 <= cols; c2++) { // Calculate sum in O(1) using prefix sum matrix int sum = prefixSum[r2][c2] - prefixSum[r1 - 1][c2] - prefixSum[r2][c1 - 1] + prefixSum[r1 - 1][c1 - 1]; if (sum == target) { count++; } } } } } return count; }}Complexity
Time
O(R^2 * C^2). Pre-computation takes O(R * C). The four nested loops to check every submatrix dominate the complexity.
Space
O(R * C) to store the 2D prefix sum matrix.
Trade-offs
Pros
Significantly faster than the pure brute-force approach.
Reduces the sum calculation from O(R*C) to O(1).
Cons
Still too slow for the given constraints, as O(R^2 * C^2) is too large.
Uses extra space for the prefix sum matrix.
This approach involves iterating through every possible submatrix, calculating the sum of its elements, and checking if the sum equals the target.
Algorithm
- Initialize a counter
countto 0. - Iterate through each possible starting row
r1from 0 torows-1. - Inside, iterate through each possible starting column
c1from 0 tocols-1. - Inside, iterate through each possible ending row
r2fromr1torows-1. - Inside, iterate through each possible ending column
c2fromc1tocols-1. - For each submatrix defined by
(r1, c1, r2, c2), calculate its sum by iterating fromr1tor2andc1toc2. - If the sum equals
target, incrementcount. - Return
count.
Walkthrough
We define a submatrix by its top-left corner (r1, c1) and its bottom-right corner (r2, c2). We use four nested loops to iterate through all possible combinations of r1, c1, r2, and c2. For each defined submatrix, we use two more nested loops to iterate through its elements and calculate their sum. If the calculated sum matches the target, we increment a counter. This method is very intuitive but computationally expensive due to the six nested loops.
class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { int rows = matrix.length; int cols = matrix[0].length; int count = 0; // Iterate over all possible top-left corners (r1, c1) for (int r1 = 0; r1 < rows; r1++) { for (int c1 = 0; c1 < cols; c1++) { // Iterate over all possible bottom-right corners (r2, c2) for (int r2 = r1; r2 < rows; r2++) { for (int c2 = c1; c2 < cols; c2++) { // Calculate the sum of the submatrix defined by (r1, c1) and (r2, c2) int sum = 0; for (int i = r1; i <= r2; i++) { for (int j = c1; j <= c2; j++) { sum += matrix[i][j]; } } // Check if the sum equals the target if (sum == target) { count++; } } } } } return count; }}Complexity
Time
O(R^3 * C^3), where R is the number of rows and C is the number of columns. There are O(R^2 * C^2) submatrices, and for each, the sum calculation can take up to O(R * C) time.
Space
O(1), as we only use a few variables to store sums and loop indices.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error for larger inputs.
This is the most efficient approach. The core idea is to fix a pair of columns (a left column c1 and a right column c2) and then treat the problem as finding the number of subarrays that sum to the target in a 1D array. This 1D array is formed by summing up the elements between c1 and c2 for each row.
Algorithm
- Initialize
count = 0. - Iterate through all possible left columns
c1from0tocols-1. - For each
c1, create a 1D arrayrowSumof sizerows, initialized to zeros. - Iterate through all possible right columns
c2fromc1tocols-1.- Update
rowSumby adding the elements of columnc2. NowrowSum[r]holds the sum ofmatrix[r][c1...c2]. - Solve the 1D "subarray sum equals k" problem on
rowSumusing a HashMap. - Initialize
map = {0: 1}andcurrentSum = 0. - Iterate through
rowSum:- Update
currentSum. - Add
map.getOrDefault(currentSum - target, 0)to the totalcount. - Increment the frequency of
currentSumin the map.
- Update
- Update
- Return
count.
Walkthrough
We iterate through all possible pairs of left and right columns, c1 and c2. For each pair of columns, we create a 1D array, let's call it rowSum, where rowSum[i] stores the sum of elements in the i-th row from column c1 to c2. We can build this rowSum array efficiently. We start with c1 and iterate c2 from c1 to the last column. For each c2, we update the rowSum array by adding the elements of column c2. Now, for the current rowSum array, we need to solve the classic problem: "Find the number of subarrays that sum to target". This 1D problem can be solved in linear time using a HashMap. We iterate through rowSum, keeping track of the currentPrefixSum. For each currentPrefixSum, we check if currentPrefixSum - target exists in our HashMap. If it does, it means there's a subarray ending at the current position with the desired sum. The value in the map tells us how many such starting points exist. We initialize the map with a (0, 1) entry to handle subarrays that start from the beginning of rowSum. By summing up the counts from all pairs of columns, we get the total number of submatrices.
import java.util.HashMap;import java.util.Map; class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { int rows = matrix.length; int cols = matrix[0].length; int count = 0; // Iterate over all possible pairs of columns for (int c1 = 0; c1 < cols; c1++) { int[] rowSum = new int[rows]; for (int c2 = c1; c2 < cols; c2++) { // Update rowSum array for the current columns c1 to c2 for (int r = 0; r < rows; r++) { rowSum[r] += matrix[r][c2]; } // Solve the 1D subarray sum problem for the current rowSum array Map<Integer, Integer> prefixSumCount = new HashMap<>(); prefixSumCount.put(0, 1); int currentSum = 0; for (int sum : rowSum) { currentSum += sum; count += prefixSumCount.getOrDefault(currentSum - target, 0); prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1); } } } return count; }}Complexity
Time
O(C^2 * R). We have two nested loops for columns (O(C^2)) and an inner loop for rows (O(R)). If R > C, we can optimize by iterating over rows first, making the complexity O(min(R, C)^2 * max(R, C)).
Space
O(R) to store the `rowSum` array and the HashMap. If we iterate over rows first (when R > C), it would be O(C). So, O(max(R, C)).
Trade-offs
Pros
Most efficient approach that passes the given constraints.
Cleverly reduces a 2D problem to a series of 1D problems, which can be solved efficiently.
Cons
Can be less intuitive to come up with compared to the more direct approaches.
Solutions
Solution
class Solution {public int numSubmatrixSumTarget(int[][] matrix, int target) { int m = matrix.length, n = matrix[0].length; int ans = 0; for (int i = 0; i < m; ++i) { int[] col = new int[n]; for (int j = i; j < m; ++j) { for (int k = 0; k < n; ++k) { col[k] += matrix[j][k]; } ans += f(col, target); } } return ans; }private int f(int[] nums, int target) { Map<Integer, Integer> d = new HashMap<>(); d.put(0, 1); int s = 0, cnt = 0; for (int x : nums) { s += x; cnt += d.getOrDefault(s - target, 0); d.merge(s, 1, Integer : : sum); } return cnt; }}class Solution {public: int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) { int m = matrix.size(), n = matrix[0].size(); int ans = 0; for (int i = 0; i < m; ++i) { vector<int> col(n); for (int j = i; j < m; ++j) { for (int k = 0; k < n; ++k) { col[k] += matrix[j][k]; } ans += f(col, target); } } return ans; } int f(vector<int> &nums, int target) { unordered_map<int, int> d{{0, 1}}; int cnt = 0, s = 0; for (int &x : nums) { s += x; if (d.count(s - target)) { cnt += d[s - target]; } ++d[s]; } return cnt; }};class Solution: def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int: def f(nums: List[int]) -> int: d = defaultdict(int) d[0] = 1 cnt = s = 0 for x in nums: s += x cnt += d[s - target] d[s] += 1 return cnt m, n = len(matrix), len(matrix[0]) ans = 0 for i in range(m): col = [0] * n for j in range(i, m): for k in range(n): col[k] += matrix[j][k] ans += f(col) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.