Number of Submatrices That Sum to Target (2024)

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 <= 100
• 1 <= matrix[0].length <= 100
• -1000 <= matrix[i] <= 1000
• -10^8 <= target <= 10^8

1. For a matrix, what is the prefix sum ?
2. sum[x] [y] is the sum of submatrix
3. (The upper left corner is matrix[0] [0], the lower right corner is matrix[x] [y])

1. How to calculate the sum of all submatrices whose upper left corners are matrix[0] [0] ？
2. Step 1. Calculate the prefix sum of each line.

// Like the one-dimensional prefix sum, 
// in order to prevent index out of range and facilitate calculations, 
// we add an extra column with all 0s at the forefront.
 int line = matrix.length;
 int column = matrix[0].length + 1;
 int[][] sum = new int[line][column]; // Initialization default is all 0 
for (int l = 0; l < sum.length; l++){ // start from the second column 
 for (int c = 1; c < sum[0].length; c++){ 
sum[l][c] = sum[l][c - 1] + matrix[l][c - 1]; // "c - 1",because of an extra column. 
 }
 }

1. Step 2. Using the prefix sum of each line to calculate the sum of submatrix.

• sum[1][2] = sum[1][2] + sum[0][2]; // green + orang
• sum[2][2] = sum[2][2] + sum[1][2] + sum[0][2]; // blue + green + orange

1. So, to caculate any sum of submatrices whose upper left corner are matrix[0] [0].

int sumOfSubMatrix = 0; 
for(int l = 0; l < line; l++){ 
 sumOfSubMatrix += sum[l][column]; // one of submatrices 
}

1. How to find all submatrices ?
2. Any submatrix needs any two rows and any two columns to form, that is to say, four variables and four nested loops are required.

// Use double nested "for" loop to select any two columns 
for (int start = 0; start < column; start++){ 
 for (int end = start + 1; end < column; end++ ){ 
 // ... // Then Use double nested "for" loop to select any two lines 
 } 
 }

1. Convert 2D to 1D
2. Step 1 : Use the prefix sum of each row to calculate the matrix sum between the “start” column and “end” column.

1. Step 2 : Rotate it 90 degrees to the left, it can be regarded as a one-dimensional array.

1. Then the problem is transformed into how many sub-arrays whose sum == target ?
2. Step 3 : In the same way, we can use hashmap to optimize the double nested loop for any two lines, and only need one loop

int sumOfSubMatrix = 0; 
Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
map.put(0, 1); 
for(int l = 0; l < line; l++){ 
 // prefix sum 
 sumOfSubMatrix += sum[l][end] - sum[l][start]; 
 if (map.containsKey(sumOfSubMatrix - target)) 
count += map.get(sumOfSubMatrix - target); 
map.put(sumOfSubMatrix, map.getOrDefault(sumOfSubMatrix, 0) + 1);

1. What’s the meaning of this sentence ?

• “Any submatrix needs any two rows and any two columns to form, that is to say, four variables and four nested loops are required.”
• eg. |0| is the submatrix I want to find, whose index is [0][0]
  In the “sum”, the column 1 corresponds to column 0 in “matrix”. SO we bound the area like this

Since we have done prefix sum for every line, we need to do sum[line][end_column] — sum[line][start_column], and in this case elements in start_column is all 0, when we subtract sum[line][0], It actually did nothing.

Also, since “end_cloumn” starts from “end_cloumn = start_column + 1”, it is impossible to treat the first column of “sum” as part of our result.

class Solution {
 public int numSubmatrixSumTarget(int[][] matrix, int target) {
 int count = 0;
 int row = matrix.length;
 int column = matrix[0].length + 1;
 int[][] sum = new int[row][column];
 for (int i = 0; i < sum.length; i++){
 for (int j = 1; j < sum[0].length; j++){
 sum[i][j] = sum[i][j - 1] + matrix[i][j - 1];
 }
 }
 for (int start = 0; start < column; start++){
 for (int end = start + 1; end < column; end++ ){
 int sumOfSubMatrix = 0;
 Map<Integer, Integer> map = new HashMap<Integer, Integer>();
 map.put(0, 1);
 for(int l = 0; l < row; l++){
 sumOfSubMatrix += sum[l][end] - sum[l][start];
 if (map.containsKey(sumOfSubMatrix - target))
 count += map.get(sumOfSubMatrix - target);
 map.put(sumOfSubMatrix, map.getOrDefault(sumOfSubMatrix, 0) + 1);
 }
 }
 }
 return count;
 }
}

If you Liked My Explanation

You can connect with me on Linkedin for more Reads like this!

Here is my linkedin Profile https://www.linkedin.com/in/roshan-jha-20m10/