Number of Submatrices That Sum to Target

How it works

Similar to the horizontal approach, but we fix column bounds instead of row bounds. For each pair of columns (c1 to c2), we maintain a running row sum and apply the hash map technique vertically. This can be more efficient when there are fewer columns than rows.

Steps

1. For each pair of columns (c1, c2):
   • Maintain a row prefix array where rowPrefix[r] stores the sum of elements in row r from column c1 to c2.
   • Apply the 1D subarray sum technique: use a hash map to count prefix sums differing by the target.
2. For each row, update the row prefix and check against the hash map.
3. Return the total count.

Complexity

• Time complexity: O(m * n ^ 2)
• Space complexity: O(m)

Where m is the number of rows and n is the number of columns of the given matrix.

Things to watch for

Incorrect 2D Prefix Sum Formula

The inclusion-exclusion principle for 2D prefix sums is error-prone. The correct formula is subSum[r2][c2] - subSum[r1-1][c2] - subSum[r2][c1-1] + subSum[r1-1][c1-1]. Forgetting to add back the top-left corner (which gets subtracted twice) leads to incorrect results.

Off-by-One Errors with Boundary Conditions

When computing prefix sums or querying submatrix sums, accessing indices like r1-1 or c1-1 when r1=0 or c1=0 causes out-of-bounds errors. You must handle these boundary cases explicitly by checking if the index is valid before accessing.

Forgetting to Initialize Hash Map with Zero

In the 1D subarray sum reduction, the hash map must be initialized with {0: 1} to count subarrays starting from the beginning of the row range. Without this initialization, you miss all submatrices whose sum equals exactly the target from the leftmost column.

Choosing the Wrong Dimension to Iterate

The optimal approach iterates over the smaller dimension for the outer loops. If you iterate over rows when there are many more rows than columns, the time complexity becomes worse than necessary. Always consider iterating over min(m, n) for the pair loops.

Integer Overflow with Large Matrices

When the matrix contains large values (positive or negative), prefix sums can overflow 32-bit integers. Use 64-bit integers or appropriate data types to handle cumulative sums, especially when the matrix is large.

from typing import List
from collections import defaultdict

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0

        for c1 in range(COLS):
            row_prefix = [0] * ROWS
            for c2 in range(c1, COLS):
                for r in range(ROWS):
                    row_prefix[r] += matrix[r][c2]

                count = defaultdict(int)
                count[0] = 1
                cur_sum = 0
                for r in range(ROWS):
                    cur_sum += row_prefix[r]
                    res += count[cur_sum - target]
                    count[cur_sum] += 1

        return res

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int ROWS = matrix.size(), COLS = matrix[0].size(), res = 0;

        for (int c1 = 0; c1 < COLS; c1++) {
            vector<int> rowPrefix(ROWS, 0);
            for (int c2 = c1; c2 < COLS; c2++) {
                for (int r = 0; r < ROWS; r++) {
                    rowPrefix[r] += matrix[r][c2];
                }

                unordered_map<int, int> count;
                count[0] = 1;
                int curSum = 0;
                for (int r = 0; r < ROWS; r++) {
                    curSum += rowPrefix[r];
                    res += count[curSum - target];
                    count[curSum]++;
                }
            }
        }
        return res;
    }
};