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.
1import java.util.*;
2
3The Java solution mirrors the logic of other language implementations, using nested loops to evaluate all possible submatrices via cumulative sums in a row stripe.