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.
1function numSubmatrixSumTarget(matrix, target) {
2 const rows = matrix.length;
3 const cols = matrix[0].length;
4 let result = 0;
5 for (let row = 0; row < rows; row++) {
6 const prefixSum = Array(cols).fill(0);
7 for (let r = row; r < rows; r++) {
8 for (let c = 0; c < cols; c++) {
9 prefixSum[c] += matrix[r][c];
10 }
11 let currentSum = 0;
12 const sumCount = {0: 1};
13 for (const sumVal of prefixSum) {
14 currentSum += sumVal;
15 if (sumCount[currentSum - target] !== undefined) {
16 result += sumCount[currentSum - target];
17 }
18 sumCount[currentSum] = (sumCount[currentSum] || 0) + 1;
19 }
20 }
21 }
22 return result;
23}The JavaScript code follows a similar approach, iterating over potential row pairs and maintaining cumulative sums using a hash map. For each possible submatrix, it checks if the target can be reached and counts such submatrices.
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.