Number of Submatrices That Sum to Target

hard prefix sum hash map matrix

Problem

Given a matrix and a target, return the number of non-empty submatrices that sum to target. A submatrix is defined by a contiguous range of rows and a contiguous range of columns; two submatrices are different if they differ in their top-left or bottom-right coordinate (even if the values are identical).

Inputmatrix = [[1, -1], [-1, 1]], target = 0

Output5

Five submatrices sum to 0: each of the two rows ([1,-1] and [-1,1]), each of the two columns ([1,-1] and [-1,1]), and the whole 2×2 matrix.

matrix (rows separated by ";", values by ",")

target

def num_submatrix_sum_target(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    total = 0
    for top in range(rows):
        col_sum = [0] * cols
        for bottom in range(top, rows):
            for c in range(cols):
                col_sum[c] += matrix[bottom][c]
            seen = {0: 1}
            prefix = 0
            for c in range(cols):
                prefix += col_sum[c]
                total += seen.get(prefix - target, 0)
                seen[prefix] = seen.get(prefix, 0) + 1
    return total

function numSubmatrixSumTarget(matrix, target) {
  const rows = matrix.length, cols = matrix[0].length;
  let total = 0;
  for (let top = 0; top < rows; top++) {
    const colSum = new Array(cols).fill(0);
    for (let bottom = top; bottom < rows; bottom++) {
      for (let c = 0; c < cols; c++) colSum[c] += matrix[bottom][c];
      const seen = new Map([[0, 1]]);
      let prefix = 0;
      for (let c = 0; c < cols; c++) {
        prefix += colSum[c];
        total += seen.get(prefix - target) || 0;
        seen.set(prefix, (seen.get(prefix) || 0) + 1);
      }
    }
  }
  return total;
}

class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int rows = matrix.length, cols = matrix[0].length, total = 0;
        for (int top = 0; top < rows; top++) {
            int[] colSum = new int[cols];
            for (int bottom = top; bottom < rows; bottom++) {
                for (int c = 0; c < cols; c++) colSum[c] += matrix[bottom][c];
                Map<Integer, Integer> seen = new HashMap<>();
                seen.put(0, 1);
                int prefix = 0;
                for (int c = 0; c < cols; c++) {
                    prefix += colSum[c];
                    total += seen.getOrDefault(prefix - target, 0);
                    seen.merge(prefix, 1, Integer::sum);
                }
            }
        }
        return total;
    }
}

int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size(), cols = matrix[0].size(), total = 0;
    for (int top = 0; top < rows; top++) {
        vector<int> colSum(cols, 0);
        for (int bottom = top; bottom < rows; bottom++) {
            for (int c = 0; c < cols; c++) colSum[c] += matrix[bottom][c];
            unordered_map<int, int> seen{{0, 1}};
            int prefix = 0;
            for (int c = 0; c < cols; c++) {
                prefix += colSum[c];
                total += seen.count(prefix - target) ? seen[prefix - target] : 0;
                seen[prefix]++;
            }
        }
    }
    return total;
}

Explanation

The big idea is to turn a 2D problem into a 1D one. We fix a top row and a bottom row, then squash all the rows in between into a single array colSum where each entry is the sum of one column across those rows. Any submatrix using exactly those top and bottom rows now corresponds to a contiguous slice of colSum.

So the question "how many submatrices sum to target?" becomes "how many subarrays of colSum sum to target?" repeated over every pair of rows. To grow the row range efficiently, when we drop the bottom row down by one we just add that new row into colSum rather than recomputing it.

Counting subarrays with a given sum uses the classic prefix-sum hash map. As we walk colSum building a running prefix, a subarray ending here sums to target whenever some earlier prefix equals prefix - target. The seen map (seeded with {0: 1}) tells us how many times that earlier prefix occurred, and we add that to the total.

Example: matrix = [[1, -1], [-1, 1]], target = 0. Sweeping all row pairs finds five zero-sum submatrices — the two rows, the two columns, and the whole grid — giving the answer 5.

Time: O(m² · n) Space: O(n)