Sponsored
Sponsored
In this approach, dynamically calculate prefix sums along rows. Iterate through all pairs of rows to create a strip of the matrix and calculate the sum of each potential submatrix contained within that strip using a hash map.
Time Complexity: O(N^2 * M), where N is number of rows and M is number of columns.
Space Complexity: O(M) for the prefix sum array.
1def numSubmatrixSumTarget(matrix, target):
2 from collections import defaultdict
3 rows, cols = len(matrix), len(matrix[0])
4 result = 0
5 for row in range(rows):
6 prefix_sum = [0] * cols
7 for r in range(row, rows):
8 for c in range(cols):
9 prefix_sum[c] += matrix[r][c]
10 current_sum = 0
11 sum_count = defaultdict(int)
12 sum_count[0] = 1
13 for sum_val in prefix_sum:
14 current_sum += sum_val
15 result += sum_count[current_sum - target]
16 sum_count[current_sum] += 1
17 return resultThe Python solution uses a double loop over possible row pairs and calculates cumulative sums for the columns between those rows. Then, using a hash map, it calculates how many segments have a certain sum value, looking to reach our target sum.
This approach involves examining every possible submatrix, calculating the sum, and checking if it equals the target. While not optimal, it provides a straightforward solution at the expense of efficiency.
Time Complexity: O(N^3 * M^3), due to the multiple nested loops over possible submatrices.
Space Complexity: O(M) for the interim sums.
1#include <vector>
2using namespace std;
3
4int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
5 int n = matrix.size(), m = matrix[0].size();
int result = 0;
for (int r1 = 0; r1 < n; ++r1) {
vector<int> sums(m);
for (int r2 = r1; r2 < n; ++r2) {
for (int c = 0; c < m; ++c) {
sums[c] += matrix[r2][c];
}
for (int c1 = 0; c1 < m; ++c1) {
int sum = 0;
for (int c2 = c1; c2 < m; ++c2) {
sum += sums[c2];
if (sum == target) {
result++;
}
}
}
}
}
return result;
}The C++ solution uses a triple nested loop to cover all possible submatrices. It maintains an intermediate array sums to hold row-wise sums between two row indices, allowing inner loops to focus on column sums.