HardNo. 1074

Number of Submatrices That Sum to Target — LeetCode 1074 Python Solution

Pattern
Prefix Sum
Topics
Array, Hash Table, Matrix, Prefix Sum
Reading time
4 min

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.

Example

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

Python solution

PythonSolution
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

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1074. Number of Submatrices That Sum to Target is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
1072Flip Columns For Maximum Number of Equal RowsMedium
0036Valid SudokuMedium
0037Sudoku SolverHard
0073Set Matrix ZeroesMedium
0523Continuous Subarray SumMedium
0525Contiguous ArrayMedium

Frequently asked questions

How hard is LeetCode 1074. Number of Submatrices That Sum to Target?

LeetCode 1074. Number of Submatrices That Sum to Target is rated Hard on LeetCode.

What is the time complexity of LeetCode 1074. Number of Submatrices That Sum to Target?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1074. Number of Submatrices That Sum to Target?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1074. Number of Submatrices That Sum to Target cover?

LeetCode 1074. Number of Submatrices That Sum to Target is tagged Array, Hash Table, Matrix and Prefix Sum on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.