**CATEGORY: HARD**

**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[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 different coordinate: for example, if `x1 != x1'`

.

**Examples**

**First Example :**

1 2 3 | Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 Output: 4 Explanation: The four 1x1 submatrices that only contain 0. |

**Second Example :**

1 2 3 | Input: matrix = [[1,-1],[-1,1]], target = 0 Output: 5 Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix. |

**Third Example :**

1 2 | Input: matrix = [[904]], target = 0 Output: 0 |

**Constraints:**

`1 <= matrix.length <= 100`

`1 <= matrix[0].length <= 100`

`-1000 <= matrix[i][j] <= 1000`

`-10^8 <= target <= 10^8`

**Solution Approach**

**Solution Logic**

In this problem of “Number of Submatrices That Sum to Target”, the goal is to determine the count of non-empty submatrices within a given matrix that sum up to a specified target. The approach involves traversing the matrix, calculating cumulative sums, and efficiently checking for the desired target.

In tackling the “Number of Submatrices That Sum to Target” problem, our primary goal is to devise a strategy for counting non-empty submatrices within a given matrix that collectively sum up to a specified target. To achieve this, our approach employs a meticulous row traversal method coupled with the computation of cumulative sums. This cumulative sum technique proves pivotal in the identification of potential submatrices. A crucial aspect of our solution involves utilizing a HashMap to store cumulative sums and their corresponding occurrences. This HashMap acts as a dynamic record-keeper, facilitating an organized exploration of possible submatrices.

The systematic exploration unfolds through nested loops, with the outer loop determining the starting column for submatrix formation. Meanwhile, the inner loop dynamically extends the submatrix to reach the last element in the selected column. Within these nested loops, an additional inner loop iterates over the rows, forming the matrix as it progresses. The cumulative sums are computed, updating the HashMap with each iteration. This strategic approach ensures comprehensive coverage of all possible submatrices, a crucial factor for the algorithm’s efficiency.

**Time Complexity: O(n^3)**

The time complexity of this approach is O(cols^2 * rows), where `cols`

is the number of columns in the matrix and `rows`

is the number of rows. This is due to the nested loops that iterate over columns and rows, and within those loops, another loop iterates over rows. The cumulative sum computation, HashMap operations, and target sum checks are all done within these nested loops.

**Space Complexity: O(n^2)**

The space complexity is **O(rows * cols)** due to the space used for storing the cumulative sums in the matrix. Additionally, the HashMap used for tracking cumulative sums and their occurrences contributes to the space complexity. In the worst case, the HashMap may store cumulative sums for each element in the matrix, resulting in a space complexity proportional to the number of elements in the matrix. Therefore, the overall space complexity is **O(rows * cols)**.

**Solution Code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | public int numSubmatrixSumTarget(int[][] matrix, int target) { int rows = matrix.length, columns = matrix[0].length; // Step 1: Cumulative Sum Computation for Each Row for (int i = 0; i < rows; i++) { for (int j = 1; j < columns; j++) { matrix[i][j] += matrix[i][j - 1]; } } // Step 2: Initialize Result Variable and HashMap int result = 0; HashMap<Integer, Integer> sumMap = new HashMap<>(); // Step 3: Main Iteration Over Columns (Starting and Ending Columns) for (int i = 0; i < columns; i++) { for (int j = i; j < columns; j++) { // Step 4: Initialize Variables for Submatrix Computation sumMap.clear(); sumMap.put(0, 1); int cur = 0; // Step 5: Innermost Loop Over Rows for Submatrix Computation for (int k = 0; k < rows; k++) { cur += matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0); // Step 6: Target Check and Update Result Count result += sumMap.getOrDefault(cur - target, 0); // Step 7: Update HashMap with Current Cumulative Sum sumMap.put(cur, sumMap.getOrDefault(cur, 0) + 1); } } } // Step 8: Return Final Result return result; } |

**Code Logic**

The code implementation commences by initializing variables corresponding to the number of rows and columns in the given matrix. The row traversal phase involves updating each element in a row to represent the cumulative sum from left to right. This cumulative sum computation is a foundational step, enabling the straightforward calculation of the sum for any submatrix under consideration. The main computational logic is encapsulated within the nested loops: the outer loop sets the starting column for submatrix formation, and the inner loop dynamically extends the submatrix to the last element in the chosen column.

Within this structured loop arrangement, an additional inner loop iterates over the rows, contributing to the formation of the matrix. The HashMap, initialized to keep track of cumulative sums and their occurrences, plays a crucial role in the efficiency of the algorithm. At each step, the code checks for the target sum, incrementing the count of submatrices that meet the specified criteria. This strategic use of loops, cumulative sums, and a HashMap not only ensures the algorithm’s effectiveness but also enhances its adaptability to various matrix scenarios.

**Code Breakdown**

1 2 3 4 5 6 7 | public int numSubmatrixSumTarget(int[][] matrix, int target) { int rows = matrix.length, columns = matrix[0].length; for (int i = 0; i < rows; i++) { for (int j = 1; j < columns; j++) { matrix[i][j] += matrix[i][j - 1]; } } |

- This segment of code iterates through each row of the matrix and calculates cumulative sums for each element. The cumulative sum is computed from the leftmost element to the current position in the row. This step is crucial for efficiently computing submatrix sums later.

1 2 | int result = 0; HashMap<Integer, Integer> sumMap = new HashMap<>(); |

- Here, we initialize variables:
`result`

to store the final count of submatrices with the target sum, and`sumMap`

, a HashMap to track cumulative sums and their occurrences during the iteration.

1 2 | for (int i = 0; i < columns; i++) { for (int j = i; j < columns; j++) { |

- These nested loops iterate over potential starting and ending columns of the submatrix. The variable
`i`

represents the starting column, and`j`

represents the ending column.

1 2 3 | sumMap.clear(); sumMap.put(0, 1); int cur = 0; |

- Inside the nested loops, we clear the HashMap (
`sumMap`

) and initialize it with an entry for an empty submatrix (cumulative sum of 0). The variable`cur`

is initialized to track the cumulative sum during the submatrix computation.

1 2 | for (int k = 0; k < rows; k++) { cur += matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0); |

- This innermost loop iterates over the rows of the current submatrix. It updates the cumulative sum (
`cur`

) based on the cumulative sums matrix. The expression`matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0)`

calculates the element value for the current submatrix.

1 | result += sumMap.getOrDefault(cur - target, 0); |

- Within the same loop, we check if the complement of the current cumulative sum (
`cur`

) with respect to the target is present in the HashMap (`sumMap`

). If found, we increment the result count (`result`

) by the number of occurrences recorded in the HashMap.

1 2 3 4 | sumMap.put(cur, sumMap.getOrDefault(cur, 0) + 1); } } } |

- After completing the innermost loop, we update the HashMap (
`sumMap`

) with the current cumulative sum and its occurrences.

1 2 | return result; } |

- Finally, we return the final count of submatrices with the target sum as the result.

Leetcode Link for Maximum Frequency Stack – https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description/

For more Leetcode-explained solutions visit Leetcode Solutions. If you like capture-the-flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page. Happy Leetcoding 🙂