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, andj
iterates fromi
to the last row,m
. For each pair(i,j)
, we are considering a horizontal slab of the matrix from rowi
to rowj
. -
For each of these horizontal slabs, we construct an array
col
which will hold the cumulative sums for thek
-th column from rowi
to rowj
. This transformation essentially 'flattens' our 2D submatrix slab into a 1D array of sums. -
With this 1D array
col
, we invoke the functionf(nums)
. This function uses a dictionaryd
to keep track of the number of times a specific prefix sum has occurred. We initialized
with the base cased[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 incol
), we add each number to a running sums
. For each element, we look at the current sums
and check how many times we have seen a sum ofs - target
. Ifs - target
is ind
, it means that there is a submatrix ending at the current element which adds up totarget
. We incrementcnt
by the count ofs - target
fromd
. -
After checking for the count of
s - target
, we updated
by incrementing the count ofs
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 totarget
for our current slab of rows betweeni
andj
. We add this to our totalans
. -
After the loops are finished,
ans
contains the total count of submatrices that add up totarget
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 EvaluatorExample 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.
-
Initialize Ans: Start by initializing
ans
to 0. This will be used to store the final count of submatrices. -
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 andj
iterates fromi
to the bottom row. -
Transform to 1D
col
Array: For each fixed vertical boundary(i, j)
, we create a 1Dcol
array representing cumulative sums of each column from rowi
to rowj
.For
i = 0
andj = 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
-
Function
f(nums)
Calculation: Call functionf(cols)
which uses a dictionaryd
to keep track of prefix sums.When we consider
i = 0
andj = 1
, we invokef([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. -
Update Ans: Add the count from the function
f(nums)
toans
. Repeat the process for each vertical slab defined by(i, j)
. -
Final Answer: After iterating through all pairs of
(i, j)
, summing up the counts of submatrices from eachf(nums)
, we end up with the totalans
.
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)
wherem
is the number of rows. Inside these loops, we iterate through the columns for each submatrix, which adds another factor ofn
, wheren
is the number of columns. Thus, the iteration through the submatrices isO(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 ofO(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 ofO(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 usesO(n)
space, wheren
is the number of columns. This array stores the cumulative sum of the columns for the current submatrix. -
The
d
dictionary in functionf
will store at mostn + 1
key-value pairs, wheren
is the length ofnums
(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 ford
isO(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.
Which data structure is used to implement priority queue?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!