Leetcode 1074: Number of Submatrices That Sum to Target

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 :

Second Example :

Third Example :

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

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

• 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.

• 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.

• 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.

• 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.

• 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.

• 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.

• After completing the innermost loop, we update the HashMap (sumMap) with the current cumulative sum and its occurrences.

• 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 🙂