Skip to main content

1074 - Number of Submatrices That Sum to Target

Difficulty: Hard | Pattern: Prefix Sum + Hash Map (2D Subarray Sum) | Company tags: Amazon, Google

Problem Statement​

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

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5

Approach: 2D Prefix Sum + 1D Subarray Sum — O(m² × n)​

Key insight: Reduce to the 1D problem "count subarrays with sum = target" (LeetCode 560). Fix two row bounds r1 and r2. Compute the column sums between these rows. Then use the 1D hash-map approach on this column-sum array.

Algorithm Flow​

from collections import defaultdict

def numSubmatrixSumTarget(matrix: list[list[int]], target: int) -> int:
    m, n = len(matrix), len(matrix[0])
    
    # Compute row prefix sums (in-place)
    for row in matrix:
        for j in range(1, n):
            row[j] += row[j-1]
    
    count = 0
    
    for r1 in range(m):
        col_sum = [0] * n
        for r2 in range(r1, m):
            for c in range(n):
                col_sum[c] += matrix[r2][c]
            
            # Count subarrays in col_sum that equal target
            prefix_count = defaultdict(int)
            prefix_count[0] = 1
            running = 0
            for s in col_sum:
                running += s
                count += prefix_count[running - target]
                prefix_count[running] += 1
    
    return count

Algorithm Breakdown​

  1. Row prefix sums: matrix[r][c] becomes sum of row r from column 0 to c.
  2. Fix rows r1, r2: col_sum[c] = sum of rectangle from (r1,0) to (r2,c) minus sum to left.
  3. 1D scan: For each pair (r1, r2), count column-ranges with sum = target using the prefix_sum - target hash map trick.

Complexity​

  • Time: O(m² × n) — O(m²) row pairs × O(n) 1D scan each
  • Space: O(n) for col_sum + O(n) for prefix_count hash map

This is the 2D generalization of LeetCode 560 (Subarray Sum Equals K) — understanding 560 first makes this problem much clearer.

Key Terms​

TermDefinition
Prefix sumRunning total up to an index, letting range sums be computed in O(1) via subtraction.
2D reductionCollapsing a matrix range problem into repeated 1D subarray problems by fixing row bounds.
Hash map countingStoring frequency of each prefix-sum value seen so far to count matching subarrays in O(1) lookup.
Row pair (r1, r2)The two row boundaries that define the vertical extent of every candidate submatrix.
Complementary sumThe value running - target looked up in the hash map to count valid subarrays ending at the current position.

FAQ​

Q: Can this be solved without extra space? A: Not efficiently — the O(m²·n²) brute force checks every submatrix directly without a hash map, but the O(m²·n) approach requires the prefix_count hash map to avoid a third nested loop.

Q: What if the matrix contains only non-negative numbers? A: The hash-map approach still applies, but a sliding-window technique could also work per row-pair since sums only increase — though the hash-map solution already handles negatives, so it's simpler to keep one general approach.

Q: How would this change if we wanted the largest submatrix (not count) summing to at most K? A: That becomes LeetCode 363 (Max Sum of Rectangle No Larger Than K), which uses the same row-pair reduction but a sorted-set/binary-search lookup instead of exact hash-map counting.

Q: What is the time complexity trade-off vs brute force? A: Brute force is O(m²n²) (all submatrix corners); this approach is O(m²n) by reducing the inner two dimensions to a single O(n) hash-map pass per row pair.

Q: What if target is 0 and the matrix has many zero cells? A: Every all-zero submatrix counts, and the empty-prefix prefix_count[0] = 1 seed correctly counts subarrays that sum to target starting from index 0.

Quick Revision​

  • Goal: count submatrices whose sum equals target.
  • Step 1: convert each row into a running row-prefix-sum so any horizontal range sum is O(1).
  • Step 2: fix row bounds r1, r2; build col_sum[c] = sum of column c between those rows.
  • Step 3: run the classic "subarray sum equals k" hash-map scan on col_sum.
  • Seed prefix_count = {0: 1} to handle subarrays starting at index 0.
  • For each running sum, add prefix_count[running - target] to the answer, then record running.
  • Outer loop over r1, inner loop over r2 gives O(m²) row-pair combinations.
  • Total complexity: O(m²·n) time, O(n) space.
  • This is the 2D generalization of LeetCode 560 (Subarray Sum Equals K) — master 560 first.