LeetCode: Number of Submatrices That Sum to Target

Posted on February 10, 2020July 26, 2020 by braindenny

Number of Submatrices That Sum to Target

Similar Problems:

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.

Note:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

## https://code.dennyzhang.com/number-of-submatrices-that-sum-to-target
## Basic Ideas: hashmap + sliding window
##
##  [0,1,0]
##  [1,1,1]
##  [0,1,0]
##
##    Evaluate two rows, in order to reduce 2D problem to 1D problem
##
## Complexity: Time O(n*m*m), Space O(n*m)
class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        res = 0
        n, m = len(matrix), len(matrix[0])
        # (i, j)
        presums = [[0 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(n):
            for j in range(m):
                #  (i-1, j-1)  .
                #    .       (i, j)
                presums[i+1][j+1] = presums[i+1][j] + presums[i][j+1] - presums[i][j] + matrix[i][j]

        for i in range(n):
            for j in range(i, n):
                # row i and row j. Note: two rows might be the same row
                freqs = collections.defaultdict(int)
                freqs[0] = 1
                for k in range(m):
                    # .   (i-1, k)
                    # .   (i, k)
                    # .   (j, k)
                    v = presums[j+1][k+1]-presums[i][k+1]
                    res += freqs[v-target]
                    freqs[v] += 1
        return res

Post Views: 0