Problem statement

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/

Solution

Let us define by dp[i, j, k] sum of numbers in the rectangle i <= x < j and 0 <= y < m. Why it is enough to evaluate only values on these matrices? Because then we can use 2Sum problem: any sum of elements in submatrix with coordinates a <= x < b and c <= y < d can be evaluated as difference between sum of a <= x < b, 0 <= y < d and sum of a <= x < b, 0 <= y < c. So, let us fix a and b, and say we have sums S1, S2, ... Sm. Then we want to find how many differences between these values give us our target. The idea is to calculate cumulative sums and keep counter of values, and then check how many we have (we can not use sliding window, because we can have negative values), see problem 560. Subarray Sum Equals K for more details.

So, we have in total two stages of our algorithm:

  1. Precompute all sums in rectangles of the type i <= x < j and 0 <= y < m.
  2. For each n*(n-1)/2 problems with fixed i and j, solve sumproblem in O(m) time.

Complexity

Time complexity is O(n^2m), we need it for both stages. Space complexity is the same.

Code

class Solution:
    def numSubmatrixSumTarget(self, matrix, target):
        m, n = len(matrix), len(matrix[0])
        dp, ans = {}, 0
        for k in range(m):
            t = [0] + list(accumulate(matrix[k]))
            for i, j in combinations(range(n+1), 2):
                dp[i, j, k] = dp.get((i,j,k-1), 0) + t[j] - t[i]
        
        for i, j in combinations(range(n+1), 2):
            T = Counter([0])
            for k in range(m):
                ans += T[dp[i, j, k] - target]
                T[dp[i, j, k]] += 1
                
        return ans

If you have any questions, feel free to ask. If you like solution and explanations, please Upvote!