LeetCode 1074 - Number of Submatrices That Sum to Target

LeetCode Problem 1074

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Matrix, Prefix Sum

Solution

Problem Understanding

The problem asks us to count how many non-empty rectangular submatrices inside a 2D matrix have a sum equal to a given target.

A submatrix is any contiguous rectangular region within the matrix. If we choose two row boundaries and two column boundaries, every element inside that rectangle belongs to the submatrix. The task is not to return the submatrices themselves, only the total count of all valid submatrices whose elements sum exactly to target.

The input consists of:

• A 2D integer matrix matrix
• An integer target

The output is a single integer representing the number of distinct submatrices whose total sum equals target.

The constraints are important:

• The matrix dimensions are at most 100 x 100
• Values may be negative
• The target may also be negative

The presence of negative numbers is significant because it prevents the use of techniques like sliding windows that rely on monotonicity. A valid solution must correctly handle arbitrary positive and negative values.

A naive brute-force solution would examine every possible submatrix and compute its sum independently. However, the number of submatrices in an m x n matrix is already O(m^2 * n^2), and recomputing sums repeatedly becomes far too slow.

Important edge cases include:

• Matrices containing negative numbers
• Matrices filled with zeros
• Single-cell matrices
• Large matrices where many overlapping submatrices exist
• Cases where multiple different submatrices produce the same target sum

The problem guarantees the matrix is non-empty, so we do not need to handle empty input arrays.

Approaches

Brute Force Approach

The brute-force method considers every possible submatrix.

A submatrix is uniquely determined by:

• Top row
• Bottom row
• Left column
• Right column

That means there are O(m^2 * n^2) possible submatrices.

For each submatrix, we could iterate through all cells inside the rectangle and compute its sum directly. Since a rectangle may contain up to O(m * n) cells, the total complexity becomes:

O(m^3 * n^3)

Even with prefix sums, checking every rectangle still requires:

O(m^2 * n^2)

For matrices up to 100 x 100, this can approach 10^8 operations, which is too slow in Python and unnecessarily expensive.

The brute-force method is correct because it explicitly checks every possible submatrix, but it does not scale efficiently.

Optimal Approach

The key insight is that we can reduce the 2D problem into multiple 1D subarray sum problems.

Suppose we fix two row boundaries:

• top
• bottom

For every column, we compute the sum of elements between these two rows. This converts the matrix strip into a 1D array.

Now the problem becomes:

How many subarrays in this 1D array sum to target?

This is a classic prefix sum plus hash map problem.

For a 1D array:

• Let prefixSum be the running cumulative sum.
• If prefixSum - target has appeared before, then the subarray between those positions sums to target.

Using a hash map lets us count valid subarrays in linear time.

Since there are O(m^2) pairs of rows, and each pair processes all columns in O(n), the final complexity becomes:

O(m^2 * n)

This is efficient enough for the constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m² * n² * m * n) or O(m³ * n³)	O(1)	Enumerates every submatrix and sums cells directly
Prefix Sum + Hash Map	O(m² * n)	O(n)	Converts the problem into repeated 1D subarray sum computations

Algorithm Walkthrough

Optimal Algorithm

1. First, determine the number of rows and columns in the matrix.
2. Iterate through every possible starting row top.
3. For each top, create an array called columnSums initialized with zeros. This array will accumulate sums for each column between the current pair of rows.
4. Expand the bottom boundary row by row using another loop over bottom.
5. For every column c, add matrix[bottom][c] into columnSums[c]. At this point, columnSums[c] represents the sum of all elements in column c between rows top and bottom.
6. Now the problem becomes:

Find how many subarrays in columnSums sum to target. 7. Use a prefix sum technique with a hash map:

• Initialize a hash map with {0: 1}

• Maintain a running prefix sum

• For each value:

• Add it to the running sum

• Check whether (currentSum - target) exists in the map

• If it exists, add its frequency to the answer

• Store the current prefix sum in the map

8. Repeat this process for every pair of rows.
9. Return the accumulated answer.

Why it works

Fixing the top and bottom rows guarantees that every valid submatrix between those rows corresponds exactly to a contiguous subarray across columns.

The prefix sum property ensures:

prefix[j] - prefix[i] = target

which means the subarray between i+1 and j sums to target.

By counting all previous occurrences of prefixSum - target, we efficiently count all valid subarrays ending at the current position. Since every submatrix is represented exactly once through some row pair and column interval, the algorithm counts all valid submatrices correctly.

Python Solution

from typing import List
from collections import defaultdict

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

        total_count = 0

        # Fix the top row
        for top in range(rows):

            column_sums = [0] * cols

            # Expand the bottom row
            for bottom in range(top, rows):

                # Update compressed column sums
                for col in range(cols):
                    column_sums[col] += matrix[bottom][col]

                # Count subarrays with sum == target
                prefix_count = defaultdict(int)
                prefix_count[0] = 1

                current_sum = 0

                for value in column_sums:
                    current_sum += value

                    total_count += prefix_count[current_sum - target]

                    prefix_count[current_sum] += 1

        return total_count

The implementation follows the algorithm directly.

The outer loop selects the top boundary row. For each top row, we initialize column_sums to zeros because we will gradually build vertical strip sums.

The inner loop expands the bottom boundary downward. Each time we include another row, we add its values into column_sums. This effectively compresses the 2D region between top and bottom into a 1D array.

Once we have this compressed array, we solve the classic "subarray sum equals k" problem.

The hash map prefix_count stores how many times each prefix sum has appeared. Initializing {0: 1} is essential because a prefix itself may equal the target.

Whenever:

current_sum - target

exists in the map, it means some earlier prefix creates a subarray ending at the current position whose sum equals target.

The algorithm accumulates all such matches across every row pair.

Go Solution

package main

func numSubmatrixSumTarget(matrix [][]int, target int) int {
	rows := len(matrix)
	cols := len(matrix[0])

	totalCount := 0

	for top := 0; top < rows; top++ {

		columnSums := make([]int, cols)

		for bottom := top; bottom < rows; bottom++ {

			for col := 0; col < cols; col++ {
				columnSums[col] += matrix[bottom][col]
			}

			prefixCount := map[int]int{
				0: 1,
			}

			currentSum := 0

			for _, value := range columnSums {
				currentSum += value

				totalCount += prefixCount[currentSum-target]

				prefixCount[currentSum]++
			}
		}
	}

	return totalCount
}

The Go implementation closely mirrors the Python version.

Go uses slices instead of Python lists, and maps instead of dictionaries. Unlike Python's defaultdict, Go maps return the zero value for missing keys automatically, which simplifies the logic.

Integer overflow is not an issue here because the maximum possible matrix sum remains within Go's int range under the problem constraints.

Worked Examples

Example 1

matrix =
[
  [0,1,0],
  [1,1,1],
  [0,1,0]
]

target = 0

Step 1: top = 0

Initialize:

columnSums = [0,0,0]

bottom = 0

Add row 0:

columnSums = [0,1,0]

Now count subarrays with sum 0.

Value	Running Sum	Needed Sum	Matches	Hash Map
0	0	0	1	{0:2}
1	1	1	0	{0:2,1:1}
0	1	1	1	{0:2,1:2}

Found 2 valid subarrays.

bottom = 1

Add row 1:

columnSums = [1,2,1]

No subarray sums to 0.

bottom = 2

Add row 2:

columnSums = [1,3,1]

No subarray sums to 0.

Step 2: top = 1

Reset:

columnSums = [0,0,0]

bottom = 1

columnSums = [1,1,1]

No subarray sums to 0.

bottom = 2

columnSums = [1,2,1]

No subarray sums to 0.

Step 3: top = 2

Reset:

columnSums = [0,0,0]

bottom = 2

columnSums = [0,1,0]

Again we find 2 valid subarrays.

Total answer:

4

Example 2

matrix =
[
  [1,-1],
  [-1,1]
]

target = 0

top = 0

bottom = 0

columnSums = [1,-1]

Subarrays summing to 0:

[1,-1]

Count = 1

bottom = 1

columnSums = [0,0]

Subarrays:

[0]
[0]
[0,0]

Count = 3

top = 1

bottom = 1

columnSums = [-1,1]

Subarrays:

[-1,1]

Count = 1

Total:

5

Example 3

matrix = [[904]]
target = 0

Only one submatrix exists:

[904]

Its sum is not 0, so the answer is:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m² * n)	There are O(m²) row pairs, each processed in O(n)
Space	O(n)	Hash map and compressed column array store at most O(n) values

The algorithm iterates over every pair of rows. For each pair, it processes all columns exactly once while maintaining prefix sums.

The hash map stores frequencies of prefix sums encountered in the compressed 1D array. In the worst case, there may be one distinct prefix sum per column.

This is a major improvement over enumerating all rectangles explicitly.

Test Cases

from typing import List

s = Solution()

# Example 1
assert s.numSubmatrixSumTarget(
    [[0,1,0],[1,1,1],[0,1,0]],
    0
) == 4  # Four single-cell zero submatrices

# Example 2
assert s.numSubmatrixSumTarget(
    [[1,-1],[-1,1]],
    0
) == 5  # Multiple overlapping rectangles

# Example 3
assert s.numSubmatrixSumTarget(
    [[904]],
    0
) == 0  # Single cell not equal to target

# Single cell equals target
assert s.numSubmatrixSumTarget(
    [[5]],
    5
) == 1  # One valid submatrix

# All zeros
assert s.numSubmatrixSumTarget(
    [[0,0],[0,0]],
    0
) == 9  # Every possible submatrix works

# Negative numbers
assert s.numSubmatrixSumTarget(
    [[-1,-1],[1,1]],
    0
) == 3  # Tests negative handling

# Single row
assert s.numSubmatrixSumTarget(
    [[1,2,3]],
    3
) == 2  # [3] and [1,2]

# Single column
assert s.numSubmatrixSumTarget(
    [[1],[2],[3]],
    3
) == 2  # [3] and [1,2]

# Larger mixed matrix
assert s.numSubmatrixSumTarget(
    [
        [1,2,-1],
        [-3,4,2],
        [1,-1,5]
    ],
    3
) == 4  # Mixed positive and negative values

# No matching submatrix
assert s.numSubmatrixSumTarget(
    [[1,2],[3,4]],
    100
) == 0  # No possible match

Test Case Summary

Test	Why
[[0,1,0],[1,1,1],[0,1,0]], target=0	Basic example with isolated zeros
[[1,-1],[-1,1]], target=0	Tests overlapping valid submatrices
[[904]], target=0	Single-cell negative case
[[5]], target=5	Single-cell positive case
[[0,0],[0,0]], target=0	Every submatrix valid
[[-1,-1],[1,1]], target=0	Negative numbers and cancellation
[[1,2,3]], target=3	Single-row handling
[[1],[2],[3]], target=3	Single-column handling
Mixed positive and negative matrix	General stress case
No matching submatrix	Ensures algorithm returns zero correctly

Edge Cases

Matrices Containing Negative Numbers

Negative numbers are especially important because they break many simpler techniques such as sliding windows. In a sliding window approach, expanding the window normally increases the sum, but negative values invalidate that assumption.

This implementation handles negatives correctly because it relies on prefix sums and exact difference matching rather than monotonic behavior.

All-Zero Matrices

A matrix filled with zeros creates a huge number of valid submatrices. This can expose bugs in counting logic, especially if duplicate prefix sums are not tracked properly.

The hash map stores frequencies of prefix sums rather than just existence, ensuring that every valid starting position contributes correctly to the total count.

Single Row or Single Column Matrices

When the matrix has only one row or one column, the problem effectively becomes the standard 1D subarray sum problem.

The implementation naturally handles this because fixing row boundaries still works correctly even when there is only one possible row pair.

Large Overlapping Submatrices

Some matrices contain many overlapping valid submatrices. A buggy implementation may accidentally double-count or miss some rectangles.

This solution avoids duplication because every submatrix is represented exactly once through:

• One unique pair of row boundaries
• One unique contiguous column interval

Therefore each valid rectangle contributes exactly once to the answer.