Problem statement

https://binarysearch.com/problems/Count-Submatrices-That-Sum-Target/

Solution

Equal to Leetcode 1074. Number of Submatrices That Sum to Target, but we need to use a bit faster alrogithm (with the same complexity) to get AC.

Complexity

It is O(n^2 m) for time and O(n) for additional space.

Code

class Solution:
    def solve(self, M, target):
        M = [list(accumulate(row, initial=0)) for row in M]
        n, m, ans = len(M), len(M[0]), 0

        for c1, c2 in combinations_with_replacement(range(1, m), 2):
            T = Counter([0])
            for x in accumulate([M[row][c2] - M[row][c1 - 1] for row in range(n)]):
                ans += T[x - target]
                T[x] += 1   

        return ans