Skip to main content
Talentd

Number of Submatrices That Sum to Target - Solution & Explanation

HardArrayHash TableMatrixPrefix Sum8 min readAsked at: Amazon, Meta, Google +1
Practice this problem

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.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

 

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Example 3:

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

 

Constraints:

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

Approach Overview

Problem Overview: You are given a 2D matrix and a target value. The task is to count how many rectangular submatrices have a sum equal to the target. Every possible submatrix must be considered, including single cells and larger rectangles.

Approach 1: Brute Force with Prefix Sum (O(m2 * n2) time, O(m * n) space)

The straightforward method enumerates every possible submatrix by selecting two rows and two columns that define its boundaries. To compute each submatrix sum efficiently, first build a 2D prefix sum matrix. This allows constant-time sum queries using inclusion–exclusion. You iterate through all top-left and bottom-right coordinate pairs and check whether the calculated sum equals the target. The method is simple to reason about and demonstrates a clear understanding of matrix prefix sums, but it becomes expensive because the number of submatrices grows quadratically with both dimensions.

Approach 2: Prefix Sums + Hash Map (O(m2 * n) time, O(n) space)

The optimized solution reduces the 2D problem into a sequence of 1D subarray problems. Fix two row boundaries (top and bottom). For each column, compute the cumulative sum of values between these rows, effectively compressing the matrix slice into a single array. Now the task becomes counting subarrays with sum equal to the target. This is solved using a running prefix sum and a hash table that stores how many times each prefix value has appeared. For each column, check whether currentSum - target exists in the map and add its frequency to the answer. This approach leverages ideas from array prefix-sum problems and dramatically cuts one dimension from the search space.

The key insight is converting the matrix rectangle sum into repeated subarray sum queries. By fixing row pairs and scanning columns once, you avoid enumerating every rectangle explicitly.

Recommended for interviews: The Prefix Sum + Hash Map approach is the expected solution. It shows that you can reduce a 2D problem to a known 1D pattern (subarray sum equals target) and apply hash-based prefix tracking. Mentioning the brute-force method first demonstrates understanding of the search space, while the optimized approach proves algorithmic maturity.

Approach 1: Approach using Prefix Sums and HashMap

In this approach, dynamically calculate prefix sums along rows. Iterate through all pairs of rows to create a strip of the matrix and calculate the sum of each potential submatrix contained within that strip using a hash map.

The Python solution uses a double loop over possible row pairs and calculates cumulative sums for the columns between those rows. Then, using a hash map, it calculates how many segments have a certain sum value, looking to reach our target sum.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(N^2 * M), where N is number of rows and M is number of columns.
Space Complexity: O(M) for the prefix sum array.

Try this approach in the editor →

Approach 2: Brute Force Approach

This approach involves examining every possible submatrix, calculating the sum, and checking if it equals the target. While not optimal, it provides a straightforward solution at the expense of efficiency.

The C++ solution uses a triple nested loop to cover all possible submatrices. It maintains an intermediate array sums to hold row-wise sums between two row indices, allowing inner loops to focus on column sums.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(N^3 * M^3), due to the multiple nested loops over possible submatrices.
Space Complexity: O(M) for the interim sums.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach using Prefix Sums and HashMap

Time Complexity: O(N^2 * M), where N is number of rows and M is number of columns.
Space Complexity: O(M) for the prefix sum array.

Brute Force Approach

Time Complexity: O(N^3 * M^3), due to the multiple nested loops over possible submatrices.
Space Complexity: O(M) for the interim sums.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with 2D Prefix SumO(m^2 * n^2)O(m * n)Useful for understanding submatrix enumeration or when matrix size is very small
Row Pair Compression + Hash MapO(m^2 * n)O(n)General optimal solution for large matrices and interview settings

Video Solution

Number of Submatrices That Sum to Target | Subarray Sum Equals K | Leetcode 1074 | Leetcode 560 • codestorywithMIK • 47,153 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Submatrices That Sum to Target easy or hard?
The problem is rated Hard because it requires recognizing the reduction from a 2D rectangle problem to a 1D subarray sum pattern. Once the row-compression idea is understood, the remaining logic follows the classic prefix-sum + hash-map technique.
Number of Submatrices That Sum to Target Python/Java solution
Most implementations follow the same structure: iterate over pairs of rows, maintain a column sum array, and apply the subarray-sum-with-target technique using a hash map. The logic translates cleanly to Python, JavaScript, Java, and C++.
How to solve Number of Submatrices That Sum to Target in O(n)?
A pure O(n) solution for the entire matrix is not possible because multiple row combinations must be evaluated. However, after fixing a pair of rows, the problem becomes a 1D subarray sum problem that can be solved in O(n) using prefix sums and a hash map.
What is the best approach for Number of Submatrices That Sum to Target?
The most efficient approach fixes two row boundaries and compresses the matrix into a 1D column sum array. Then it counts subarrays equal to the target using prefix sums and a hash map. This reduces the complexity to O(m^2 * n) time and O(n) space, which is significantly faster than checking every possible rectangle.
Is Number of Submatrices That Sum to Target asked at Google/Amazon/Meta?
Matrix prefix-sum and subarray-sum problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests the ability to reduce a 2D problem into repeated 1D prefix-sum computations using hash maps.
What data structure is used in Number of Submatrices That Sum to Target?
The core data structure is a hash map that tracks prefix sum frequencies while scanning columns. Combined with prefix sums and row-pair iteration, it allows constant-time lookups for previously seen sums.
What is the time complexity of Number of Submatrices That Sum to Target?
The optimal solution runs in O(m^2 * n) time, where m is the number of rows and n is the number of columns. Two rows are fixed to define the vertical boundaries, and each column is scanned once while using a hash map to count prefix sums.

Ready to solve this problem?

Practice Number of Submatrices That Sum to Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Disconnect Path in a Binary Matrix by at Most One Flip