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.

Description Hints 1 Solution Video 56:53

1074. Number of Submatrices That Sum to Target

Hard74.4% acceptance4 companies

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

Asked at 4 companies

Snapchat Amazon

Google Meta

Topics

Hints open one at a time

Hint 1

Using a 2D prefix sum, we can query the sum of any submatrix in O(1) time. Now for each (r1, r2), we can find the largest sum of a submatrix that uses every row in [r1, r2] in linear time using a sliding window.

56:53

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution