#1074

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Submatrices That Sum to Target

Count all non-empty submatrices in a given matrix whose elements sum exactly to the target using efficient scanning techniques.

array hash table matrix prefix sum

Problem Statement

Given a 2D integer matrix and a target value, return the total number of non-empty submatrices whose elements sum to exactly the target. A submatrix is defined by any rectangular region within the matrix, including all cells between two row indices and two column indices.

Two submatrices are considered different if any of their row or column boundaries differ. For example, if a submatrix spans rows x1 to x2 and columns y1 to y2, and another submatrix has at least one different boundary, they are counted separately.

Examples

Example 1

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

Output: 4

The four 1x1 submatrices that only contain 0.

Example 2

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

Output: 5

The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Example 3

Input: matrix = [[904]], target = 0

Output: 0

Example details omitted.

Constraints

1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i][j] <= 1000
-10^8 <= target <= 10^8

Solution Approach

Use 2D Prefix Sums

Compute prefix sums for every row so that any submatrix sum can be calculated in constant time. This reduces repeated summation and is critical to efficiently handle large matrices.

Iterate Row Pairs and Reduce to 1D

For each pair of rows, calculate the column-wise sum between them to create a 1D array. The problem then reduces to finding subarrays within this array that sum to the target, enabling hash map usage for quick lookup.

Apply Hash Map for Prefix Sums

Maintain a running sum and a hash map to count the number of times each cumulative sum occurs. For each position, check if runningSum - target exists in the map to increment the total count efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(rows^2 * cols) because each row pair iteration computes sums across columns with constant-time hash operations. Space complexity is O(cols) for the hash map per row pair, plus O(rows*cols) if using full 2D prefix sums.

What Interviewers Usually Probe

Watch for the O(n^4) brute force attempt; hash map optimization is expected.
They may ask about transforming 2D submatrix sums into a 1D prefix sum problem.
Check if you recognize that cumulative sum differences allow constant-time subarray queries.

Common Pitfalls or Variants

Common pitfalls

Not handling negative numbers in prefix sums correctly, leading to missing submatrices.
Double-counting submatrices due to incorrect boundary handling.
Attempting naive nested loops over all submatrices without reducing to row pairs and hash lookup.

Follow-up variants

Count submatrices where the sum is less than or equal to a target instead of exact equality.
Find the largest area submatrix with sum exactly equal to target.
Return coordinates of all submatrices summing to target instead of just the count.

FAQ

What is the main pattern used in Number of Submatrices That Sum to Target?

The pattern is array scanning combined with hash lookup, reducing 2D submatrix sum queries to 1D prefix sums for efficient counting.

Can negative numbers in the matrix affect the solution?

Yes, negative numbers require careful prefix sum handling since subarrays can sum to target even when elements are negative.

What is the time complexity for large matrices?

Using row pair iteration with hash maps, the time complexity is O(rows^2 * cols), which is much better than O(rows^2 * cols^2) brute force.

Do I need to store the full 2D prefix sum?

Storing full 2D prefix sums is optional; you can compute running column sums for row pairs to reduce space to O(cols).

How do I avoid double-counting submatrices?

Ensure each submatrix is defined by unique row and column boundaries, and carefully update the hash map only once per column iteration.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        def f(nums: List[int]) -> int:
            d = defaultdict(int)
            d[0] = 1
            cnt = s = 0
            for x in nums:
                s += x
                cnt += d[s - target]
                d[s] += 1
            return cnt

        m, n = len(matrix), len(matrix[0])
        ans = 0
        for i in range(m):
            col = [0] * n
            for j in range(i, m):
                for k in range(n):
                    col[k] += matrix[j][k]
                ans += f(col)
        return ans

Continue Practicing

#1124 longest well performing interval #1177 can make palindrome from substring #959 regions cut by slashes