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.
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.