1074. Number of Submatrices That Sum to Target

HardArrayHash TableMatrixPrefix Sum
Leetcode Link

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

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

Matrix:     Target sum:
1 2 1     ->    4
3 2 0
1 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:

    1st iteration (i=0, j=0): col = [1, 2, 1]
    2nd 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]):

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

1from collections import defaultdict
2from typing import List
3
4class Solution:
5    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
6        # Helper function to find the number of contiguous subarrays
7        # that sum up to the target value.
8        def count_subarrays_with_target_sum(nums: List[int]) -> int:
9            prefix_sum_counts = defaultdict(int)
10            prefix_sum_counts[0] = 1
11            # `count` stores the number of valid subarrays found.
12            # `prefix_sum` stores the ongoing sum of elements in the array.
13            count = prefix_sum = 0
14            for num in nums:
15                prefix_sum += num
16                # Increase count by the number of times (prefix_sum - target)
17                # has occurred before, as it represents a valid subarray.
18                count += prefix_sum_counts[prefix_sum - target]
19                # Update the count of prefix_sum occurrences.
20                prefix_sum_counts[prefix_sum] += 1
21            return count
22
23        num_rows, num_cols = len(matrix), len(matrix[0])
24        total_count = 0  # This variable will store the total submatrices found.
25        # Loop over the start row for the submatrix.
26        for start_row in range(num_rows):
27            column_sums = [0] * num_cols
28            # Loop over the end row for the submatrix.
29            for end_row in range(start_row, num_rows):
30                # Update the sum for each column to include the new row.
31                for col in range(num_cols):
32                    column_sums[col] += matrix[end_row][col]
33                # Add the count of valid subarrays in the current column sums.
34                total_count += count_subarrays_with_target_sum(column_sums)
35        # Return the total number of submatrices that sum up to the target.
36        return total_count
37
1class Solution {
2    public int numSubmatrixSumTarget(int[][] matrix, int target) {
3        int numRows = matrix.length;
4        int numCols = matrix[0].length;
5        int answer = 0;
6
7        // Loop through each row, starting from the top
8        for (int topRow = 0; topRow < numRows; ++topRow) {
9            // Initialize a cumulative column array for the submatrix sum
10            int[] cumulativeColSum = new int[numCols];
11
12            // Extend the submatrix down by increasing the bottom row from the top row
13            for (int bottomRow = topRow; bottomRow < numRows; ++bottomRow) {
14                // Update the cumulative sum for each column in the submatrix
15                for (int col = 0; col < numCols; ++col) {
16                    cumulativeColSum[col] += matrix[bottomRow][col];
17                }
18                // Count the submatrices with the sum equals the target using the helper function
19                answer += countSubarraysWithSum(cumulativeColSum, target);
20            }
21        }
22        return answer;
23    }
24
25    // Helper function to count the subarrays which sum up to the target
26    private int countSubarraysWithSum(int[] nums, int target) {
27        // Initialize a map to store the sum and frequency
28        Map<Integer, Integer> sumFrequency = new HashMap<>();
29        sumFrequency.put(0, 1);
30        int currentSum = 0;
31        int count = 0;
32
33        // Iterate through each element in the array
34        for (int num : nums) {
35            currentSum += num; // Update the running sum
36            // Increment the count by the number of times (currentSum - target) has appeared
37            count += sumFrequency.getOrDefault(currentSum - target, 0);
38            // Update the frequency map with the current sum as the key
39            // If the key exists, increment its value by 1
40            sumFrequency.merge(currentSum, 1, Integer::sum);
41        }
42        return count;
43    }
44}
45
1// Including necessary headers
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7    // Function that returns the number of submatrices that sum up to the target value.
8    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
9        int rows = matrix.size(), columns = matrix[0].size();  // Matrix dimensions
10        int answer = 0;  // Initialize the count of submatrices with sum equal to target
11
12        // Iterate over each pair of rows to consider submatrices that span from row i to j
13        for (int i = 0; i < rows; ++i) {
14            vector<int> colSums(columns, 0);  // Initialize a vector to store column sums
15            for (int j = i; j < rows; ++j) {
16                // Accumulating sum for each column between rows i and j
17                for (int k = 0; k < columns; ++k) {
18                    colSums[k] += matrix[j][k];
19                }
20                // Add to answer the count of subarrays in the summed columns that meet the target
21                answer += countSubarraysWithTarget(colSums, target);
22            }
23        }
24
25        return answer;  // Return the total count of submatrices that have sums equal to the target
26    }
27
28private:
29    // Helper function that counts the number of subarrays within a 1D array with sum equal to target
30    int countSubarraysWithTarget(vector<int>& nums, int target) {
31        unordered_map<int, int> sumFrequencies{{0, 1}};  // Initialize map with zero-sum frequency
32        int count = 0;  // Count of subarrays with sum equal to target
33        int sum = 0;    // Current sum of elements
34
35        // Iterate over the elements in the array
36        for (int num : nums) {
37            sum += num;  // Update running sum
38            // If (current sum - target) exists in the map, increment count by the number of times
39            // the (current sum - target) has been seen (this number of previous subarrays
40            // contribute to current sum equals target).
41            if (sumFrequencies.count(sum - target)) {
42                count += sumFrequencies[sum - target];
43            }
44            // Increment the frequency of the current sum in the map
45            ++sumFrequencies[sum];
46        }
47
48        return count;  // Return the count of subarrays with sum equal to target
49    }
50};
51
52// Example usage:
53// int main() {
54//     Solution sol;
55//     vector<vector<int>> matrix{{0,1,0},{1,1,1},{0,1,0}};
56//     int target = 0;
57//     int result = sol.numSubmatrixSumTarget(matrix, target);
58//     // result will hold the number of submatrices that sum up to the target
59// }
60
1// This function counts the number of submatrices that sum up to the 'target'
2function numSubmatrixSumTarget(matrix: number[][], target: number): number {
3    const numRows = matrix.length;
4    const numCols = matrix[0].length;
5    let count = 0;
6
7    // Iterate through rows
8    for (let startRow = 0; startRow < numRows; ++startRow) {
9        const columnSum: number[] = new Array(numCols).fill(0);
10
11        // Accumulate sums for all possible submatrices starting at startRow
12        for (let endRow = startRow; endRow < numRows; ++endRow) {
13            for (let col = 0; col < numCols; ++col) {
14                // Add the current row's values to the column sums
15                columnSum[col] += matrix[endRow][col];
16            }
17            // Use the helper function to count subarrays in this contiguous slice of rows that sum to target
18            count += countSubarraysWithSum(columnSum, target);
19        }
20    }
21    return count;
22}
23
24// Helper function to count the number of subarrays with sum equal to 'target'
25function countSubarraysWithSum(nums: number[], target: number): number {
26    const sumOccurrences: Map<number, number> = new Map();
27    sumOccurrences.set(0, 1); // A sum of 0 occurs once initially
28    let count = 0;
29    let currentSum = 0;
30
31    // Iterate through the array elements
32    for (const num of nums) {
33        currentSum += num;
34
35        // If the required sum that would lead to the target is found, add its occurrences to count
36        if (sumOccurrences.has(currentSum - target)) {
37            count += sumOccurrences.get(currentSum - target)!;
38        }
39
40        // Record the current sum's occurrence count, incrementing it if it already exists
41        sumOccurrences.set(currentSum, (sumOccurrences.get(currentSum) || 0) + 1);
42    }
43    return count;
44}
45

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement priority queue?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More