Number of Submatrices That Sum to Target

📘 Problem Statement

Given a 2D matrix matrix and an integer target, return the number of non-empty submatrices that sum to target.

🔍 Example

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 Output: 4 Explanation: The four 1x1 submatrices that only contain 0.

---

🛠️ Solution

We’ll reduce the 2D submatrix sum problem into multiple 1D subarray sum problems.

• Fix two rows: top and bottom.
• Compress the 2D matrix between those two rows into a 1D array of column sums.
• Now the problem becomes: how many subarrays in that 1D array sum to target? This is just Subarray Sum Equals K — which we can solve in \(O(n)\) with prefix sums and a hashmap.

---

✨ Algorithm Steps

For every pair of rows top and bottom:

• Create a 1D array sums where sums[col] = sum of elements in column col from row top to bottom.
• Count the number of subarrays in sums that sum to target using prefix sum + hashmap.

def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:

        row, col = len(matrix), len(matrix[0])  
        total_count = 0

        for upper in range(row):
            col_sum = [0] * col
            
            for lower in range(upper, row):
                
                for ix in range(col):
                    col_sum[ix] += matrix[lower][ix]
                
                # find if there is any subarray in col_sum with sum = target
                d = {}
                d[0] = 1
                prefix_sum = 0
                for sum in col_sum:
                    prefix_sum += sum
                    
                    total_count += d.get(prefix_sum - target, 0)
                    d[prefix_sum] = d.get(prefix_sum, 0) + 1 

        return total_count

---

⏱️ Time & Space Complexity

Choosing row pairs: \(O(m^2)\)

Each compression and subarray sum: \(O(n)\)

Total : \(O(m^2.n)\) where m = rows, n = columns