Simple code with explanation
Intuition\nThis solution was inspired by the Editorial and is a structure worth memorizing. Prefix sums for 2D matrix can be constructed using the following. We
# Intuition\nThis solution was inspired by the Editorial and is a structure worth memorizing. Prefix sums for 2D matrix can be constructed using the following. We recollect that prefix sums for a 2D case involves capturing the sum of all the values from cell (0,0) to cell (row, col) inclusive:\n```\nm, n = len(matrix), len(matrix[0])\n\n# add an extra row and column to avoid index checks such as i >= 1 etc.\nps = [[0]*(n+1) for _ in range(m+1)]\n\n#\n# remember that adding the extra row and column now makes \n# the reference to the original matrix 1-based indexing, matrix[i-1][j-1]\n#\nfor i in range(1, m+1):\n    for j in range(1, n+1):\n        ps[i][j] = ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1] + matrix[i-1][j-1]\n\n```\n\n# Approach\nNow we can compute the sums for any rectangular portion of the grid by using nested loops over rows and then over columns. This is what the editorial calls reducing it to a 1D problem. However to do that we\'ll use a dictionary before scanning the cols for the row, and initialize it with a count `1` for a sum of `0`:\n\n```\nfor r1 in range(1, m+1):\n    for r2 in range(r1, m+1):\n        dt = defaultdict(int)\n        dt[0] = 1\n        for col in range(1, n+1):\n            # compute sum for (r1,1) to (r2,col) \n            curr_sum = ps[r2][col] - ps[r1 - 1][col]\n\n            # check whether there exists a previous sum A s.t. curr_sum - A == target\n            count += dt[curr_sum - target]\n\n            # increment counter for curr_sum\n            dt[curr_sum] += 1\n\nreturn count\n```\n\n# Complexity\n- Time complexity:\n$O(m^2n)$ where $m$ is the number of rows and $n$ is the number of columns in matrix\n\n- Space complexity:\n$O(mn)$\n\n# Code\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m, n = len(matrix), len(matrix[0])\n\n        # 2D prefix sum\n        ps = [[0]*(n+1) for _ in range(m+1)]\n\n        for i in range(1, m+1):\n            for j in range(1, n+1):\n                ps[i][j] = ps[i][j-1] + ps[i-1][j] - ps[i-1][j-1] + matrix[i-1][j-1]\n        \n        count = 0\n        for r1 in range(1, m+1):\n            for r2 in range(r1, m+1):\n                dt = defaultdict(int)\n                dt[0] = 1\n\n                for col in range(1, n+1):\n                    curr_sum = ps[r2][col] - ps[r1 - 1][col]\n                    count += dt[curr_sum - target]\n                    dt[curr_sum] += 1\n\n        return count\n        \n```
['Python3']