Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1145. Number of Submatrices That Sum to Target

My accepted Python solution to LeetCode problem 1145, Number of Submatrices That Sum to Target, running in 369ms.

  • Difficulty: Hard
  • Python
  • Runtime 369ms
  • Memory 18.3MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 369ms, memory 18.3MB, accepted 2026-01-02.

python
class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        # Compute prefix sums for each row
        for row in matrix:
            for j in range(1, n):
                row[j] += row[j - 1]
        
        count = 0
        # For each pair of columns
        for c1 in range(n):
            for c2 in range(c1, n):
                # Use hashmap to count subarrays with sum = target
                prefix_count = {0: 1}
                curr_sum = 0
                for r in range(m):
                    # Get sum of rectangle from column c1 to c2 for row r
                    curr_sum += matrix[r][c2] - (matrix[r][c1 - 1] if c1 > 0 else 0)
                    count += prefix_count.get(curr_sum - target, 0)
                    prefix_count[curr_sum] = prefix_count.get(curr_sum, 0) + 1
        
        return count

Source