Count submatrices summing to target k. This extends 1D subarray sum counting to 2D. Fix top and bottom rows. Compress columns into 1D array (column sums). Now apply 1D hashmap technique. For each pair of rows (r1,r2), the column sums form a 1D array. Count subarrays summing to k using the hashmap method. Time: O(n2⋅m)
Time complexity: O(n2⋅m) for an n×m matrix. There are O(n2) row pairs, and each 1D pass takes O(m).
Space complexity: O(n⋅m) for the prefix sum array.