1074. Number of Submatrices That Sum to Target

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        """
        tc O(R*C*C)  sc O(R)
        main idea: refer to 363. Max Sum of Rectangle No Larger Than K
        """
        r,c = len(matrix), len(matrix[0])
        res = 0
        for col_left in range(c):
            arr = [0] * r 
            for col_right in range(col_left,c):
                for row in range(r):
                    arr[row] += matrix[row][col_right]
                res += self.countSumK(arr, target)
        return res 
    def countSumK(self, A, k):
        psum = cnt = 0
        d = {0:1}
        # psumr - psumr == k => psumr - k == psum l 
        for a in A:
            psum += a 
            if psum - k in d:
                cnt += d[psum-k]
            d[psum] = d.get(psum,0) +1 
        return cnt