1074. Number of Submatrices That Sum to Target

Problem Description

The problem provides us with a rectangular grid of numbers—a matrix—and a target sum. We are asked to count the total number of distinct submatrices where the sum of their elements is equal to the given target value. A submatrix is any contiguous block of cells within the original matrix, denoted by its top-left coordinate (x1, y1) and bottom-right coordinate (x2, y2). Each submatrix is considered unique if it differs in at least one coordinate value from any other submatrix, even if they have the same elements. This means that we're not just looking for different sets of values that add up to the target, but also different positions of those values within the matrix.

Intuition

To solve this problem, an efficient approach is required since a brute force method of checking all possible submatrices would result in an impractical solution time, particularly for large matrices. The key is to recognize that we can construct submatrices by spanning vertically from any row i to any row j and then considering all possible horizontal slices within this vertical span.

The solution uses a function f(nums) that takes a list of numbers representing the sum of elements in a column for the rows from i to j. It then utilizes a hash map (dictionary in Python) to efficiently count the submatrices which sum to target. This is done by keeping a cumulative sum s as we iterate through nums, where s is the sum of elements from the start of nums to the current position k. If s - target is found in the dictionary d, it means a submatrix ending at the current column whose sum is target has been found (since s - (s - target) = target). Every time this occurs, we add the count of s - target found so far to our total count. The dictionary is updated with the current sum, effectively storing the count of all possible sums encountered up to that position.

The outer loops iterate over the matrix to set the vertical boundaries, i and j of the submatrices. For every such vertical span, we compute the running sum of columns as if they're a single array and use f(nums) to find eligible horizontal slices. The total count from each f(nums) call accumulates in the variable ans, which gives us the final number of submatrices meeting the condition.

In essence, by breaking down the problem into a series of one-dimensional problems, where each one-dimensional problem is a vertical slice of our matrix, we can use the hash map strategy to efficiently count submatrices summing to target.

Learn more about Prefix Sum patterns.

Solution Approach

To tackle the problem, the given Python solution employs a clever use of prefix sums along with hashing to efficiently count the number of submatrices that sum to the target. Here's a walkthrough of the implementation, aligned with the algorithm and the patterns used:

• We start by initializing ans to zero, which will hold the final count of submatrices adding up to the target.

• The outer two loops fix the vertical boundaries of our submatrices. i represents the starting row, and j iterates from i to the last row, m. For each pair (i,j), we are considering a horizontal slab of the matrix from row i to row j.

• For each of these horizontal slabs, we construct an array col which will hold the cumulative sums for the k-th column from row i to row j. This transformation essentially 'flattens' our 2D submatrix slab into a 1D array of sums.

• With this 1D array col, we invoke the function f(nums). This function uses a dictionary d to keep track of the number of times a specific prefix sum has occurred. We initialize d with the base case d[0] = 1, representing a submatrix with a sum of zero, which is a virtual prefix before the start of any actual numbers.

• As we loop through nums (which are the column sums in col), we add each number to a running sum s. For each element, we look at the current sum s and check how many times we have seen a sum of s - target. If s - target is in d, it means that there is a submatrix ending at the current element which adds up to target. We increment cnt by the count of s - target from d.

• After checking for the count of s - target, we update d by incrementing the count of s by 1. This captures the idea that we now have one more submatrix (counted till the current column) that sums to ``s`.

• The return value of f(nums) gives us the number of submatrices that sum to target for our current slab of rows between i and j. We add this to our total ans.

• After the loops are finished, ans contains the total count of submatrices that add up to target across the entire matrix.

In terms of data structures, the solution relies on a 1D array to store the column sums and a dictionary to act as a hash map for storing prefix sums. The use of a hash map enables constant time checks and updates, significantly optimizing the process. This approach eliminates the need for naive checking of every possible submatrix, which would be computationally intensive.

This solution approach leverages dynamic programming concepts, particularly the idea of storing intermediary results (prefix sums and their counts) to avoid redundant calculations. This pattern is useful for problems involving contiguous subarrays or submatrices and target sums, and is a powerful tool in the competitive programming space.

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Suppose we have the following matrix and target sum:

1Matrix:     Target sum:
21 2 1     ->    4
33 2 0
41 1 1

For this example, we'll be looking to count the number of submatrices that add up to the target sum of 4.

1. Initialize Ans: Start by initializing ans to 0. This will be used to store the final count of submatrices.

2. Iterate Over Rows: Set up two nested loops to iterate over the rows to determine the vertical boundaries of potential submatrices. The variable i is the top row and j iterates from i to the bottom row.

3. Transform to 1D col Array: For each fixed vertical boundary (i, j), we create a 1D col array representing cumulative sums of each column from row i to row j.

   For i = 0 and j = 1, col would be:

   11st iteration (i=0, j=0): col = [1, 2, 1]
   22nd iteration (i=0, j=1): col = [4, 4, 1]  // Sum of rows 0 and 1

4. Function f(nums) Calculation: Call function f(cols) which uses a dictionary d to keep track of prefix sums.

   When we consider i = 0 and j = 1, we invoke f([4, 4, 1]):

   1Initialize d={0: 1} and `s` to 0.
   2Iterate the col `nums`:
   3- At col 0: s = 4. Check if s-target, which is 0, exists in d. It does. Increment ans by 1.
   4- Update d with the new sum: d = {0: 1, 4: 1}.
   5- At col 1: s = 8. There's no s-target, which is 4, in d. 
   6- Update d: d = {0: 1, 4: 2}.
   7- At col 2: s = 9. There's no s-target, which is 5, in d.
   8- Update d: d = {0: 1, 4: 2, 9: 1}.

   For this (i, j) pair, f(nums) finds 1 submatrix that adds to the target.

5. Update Ans: Add the count from the function f(nums) to ans. Repeat the process for each vertical slab defined by (i, j).

6. Final Answer: After iterating through all pairs of (i, j), summing up the counts of submatrices from each f(nums), we end up with the total ans.

In our example, we can find the following submatrices that sum to the target:

• Single submatrix from (0,0) to (1,0) with elements 1, 3 which adds up to 4.

Thus, ans for this example would be 1, indicating there is one distinct submatrix where the sum of the elements equals the target sum of 4.

Solution Implementation

Time and Space Complexity

The time complexity of the algorithm can be broken down into two parts: iterating through submatrices and calculating the sum for each submatrix to find the number of occurrences that add up to the target.

• Iterating through submatrices: It uses two nested loops that go through the rows of the matrix, which will be O(m^2) where m is the number of rows. Inside these loops, we iterate through the columns for each submatrix, which adds another factor of n, where n is the number of columns. Thus, the iteration through the submatrices is O(m^2 * n).

• Calculating the sum for each submatrix: The function f(nums: List[int]) is called for each submatrix. Inside this function, there is a for-loop of O(n) complexity because it iterates through the column cumulative sums. The operations inside the loop (accessing and updating the dictionary) have an average-case complexity of O(1).

Therefore, combining these together, the total average-case time complexity of the algorithm is O(m^2 * n^2).

For space complexity:

• The col array uses O(n) space, where n is the number of columns. This array stores the cumulative sum of the columns for the current submatrix.

• The d dictionary in function f will store at most n + 1 key-value pairs, where n is the length of nums (number of columns). This is because it records the cumulative sum of the numbers we've seen so far plus an initial zero sum. Hence, space complexity for d is O(n).

As each of the above is not dependent on one another, we take the larger of the two, which is O(n), for the overall space complexity.

In summary, the final computational complexities are:

• Time Complexity: O(m^2 * n^2)
• Space Complexity: O(n)

Learn more about how to find time and space complexity quickly using problem constraints.