Number of Submatrices That Sum to Target solution and explanation
Google
9 more videos on this problem
Number of Submatrices That Sum to Target | Subarray Sum Equals K | Leetcode 1074 | Leetcode 560codestorywithMIK · 56:53 · 47K views
Number of Submatrices That Sum to Target | Live Coding with Explanation | Leetcode - 1074Algorithms Made Easy · 11:29 · 25K views
Number of Submatrices that Sum to Target - Leetcode 1074 - PythonNeetCodeIO · 30:01 · 20K views
Leetcode 1074 | Number of Submatrices That Sum to Target | Dynamic Programming (Algorithm Explained)The Tech Granth · 21:48 · 11K views
LeetCode 1074. Number of Submatrices That Sum to Target Explanation and Solutionhappygirlzt · 12:18 · 8K views
1074. Number of Submatrices That Sum to Target | Prefix Sums | Brute - Better - OptimalAryan Mittal · 49:29 · 6K views
Leetcode 1074 Number of Submatrices That Sum to Target | Coding Decoded SDE Revision SheetCoding Decoded · 12:38 · 6K views
LeetCode 1074. Number of Submatrices That Sum to TargetHappy Coding · 20:15 · 2K views
Number of Submatrices That Sum to Target | LeetCode 1074 | Coders CampCoders Camp · 9:16 · 2K views
Leetcode - Number of Submatrices That Sum to Target (Python)Timothy H Chang · 7:42 · 2K views
The problem
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 <= 1001 <= 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.
def numSubmatrixSumTarget(matrix, target):
from collections import defaultdict
rows, cols = len(matrix), len(matrix[0])
result = 0
for row in range(rows):
prefix_sum = [0] * cols
for r in range(row, rows):
for c in range(cols):
prefix_sum[c] += matrix[r][c]
current_sum = 0
sum_count = defaultdict(int)
sum_count[0] = 1
for sum_val in prefix_sum:
current_sum += sum_val
result += sum_count[current_sum - target]
sum_count[current_sum] += 1
return resultfunction numSubmatrixSumTarget(matrix, target) {
const rows = matrix.length;
const cols = matrix[0].length;
let result = 0;
for (let row = 0; row < rows; row++) {
const prefixSum = Array(cols).fill(0);
for (let r = row; r < rows; r++) {
for (let c = 0; c < cols; c++) {
prefixSum[c] += matrix[r][c];
}
let currentSum = 0;
const sumCount = {0: 1};
for (const sumVal of prefixSum) {
currentSum += sumVal;
if (sumCount[currentSum - target] !== undefined) {
result += sumCount[currentSum - target];
}
sumCount[currentSum] = (sumCount[currentSum] || 0) + 1;
}
}
}
return result;
}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.
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.
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.
import java.util.*;
public class Solution {
public int numSubmatrixSumTarget(int[][] matrix, int target) {
int res = 0;
int rows = matrix.length, cols = matrix[0].length;
for (int r1 = 0; r1 < rows; r1++) {
int[] sums = new int[cols];
for (int r2 = r1; r2 < rows; r2++) {
for (int c = 0; c < cols; c++) {
sums[c] += matrix[r2][c];
}
for (int c1 = 0; c1 < cols; c1++) {
int sum = 0;
for (int c2 = c1; c2 < cols; c2++) {
sum += sums[c2];
if (sum == target) {
res++;
}
}
}
}
}
return res;
}
}#include <vector>
using namespace std;
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int n = matrix.size(), m = matrix[0].size();
int result = 0;
for (int r1 = 0; r1 < n; ++r1) {
vector<int> sums(m);
for (int r2 = r1; r2 < n; ++r2) {
for (int c = 0; c < m; ++c) {
sums[c] += matrix[r2][c];
}
for (int c1 = 0; c1 < m; ++c1) {
int sum = 0;
for (int c2 = c1; c2 < m; ++c2) {
sum += sums[c2];
if (sum == target) {
result++;
}
}
}
}
}
return result;
}The Java solution mirrors the logic of other language implementations, using nested loops to evaluate all possible submatrices via cumulative sums in a row stripe.
Time Complexity: O(N^3 * M^3).
Space Complexity: O(M).
Approach 3: Default Approach
function numSubmatrixSumTarget(matrix: number[][], target: number): number {
const m = matrix.length;
const n = matrix[0].length;
let ans = 0;
for (let i = 0; i < m; ++i) {
const col: number[] = new Array(n).fill(0);
for (let j = i; j < m; ++j) {
for (let k = 0; k < n; ++k) {
col[k] += matrix[j][k];
}
ans += f(col, target);
}
}
return ans;
}
function f(nums: number[], target: number): number {
const d: Map<number, number> = new Map();
d.set(0, 1);
let cnt = 0;
let s = 0;
for (const x of nums) {
s += x;
if (d.has(s - target)) {
cnt += d.get(s - target)!;
}
d.set(s, (d.get(s) || 0) + 1);
}
return cnt;
}func numSubmatrixSumTarget(matrix [][]int, target int) (ans int) {
m, n := len(matrix), len(matrix[0])
for i := 0; i < m; i++ {
col := make([]int, n)
for j := i; j < m; j++ {
for k := 0; k < n; k++ {
col[k] += matrix[j][k]
}
ans += f(col, target)
}
}
return
}
func f(nums []int, target int) (cnt int) {
d := map[int]int{0: 1}
s := 0
for _, x := range nums {
s += x
if v, ok := d[s-target]; ok {
cnt += v
}
d[s]++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach using Prefix Sums and HashMap | Time Complexity: O(N^2 * M), where N is number of rows and M is number of columns. |
| Brute Force Approach | Time Complexity: O(N^3 * M^3). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with 2D Prefix Sum | O(m^2 * n^2) | O(m * n) | Useful for understanding submatrix enumeration or when matrix size is very small |
| Row Pair Compression + Hash Map | O(m^2 * n) | O(n) | General optimal solution for large matrices and interview settings |
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.