Count submatrices summing to target . 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 , the column sums form a 1D array. Count subarrays summing to using the hashmap method. Time:
Time complexity: for an matrix. There are row pairs, and each 1D pass takes .
Space complexity: for the prefix sum array.