Fully explained intuition - 4 solutions | MUST READ | With Image
Note: that\'s a long read, but I explained the whole thinking process. It\'s going to be worth it if you want to learn and not to memorize solutions :)\n\nIf yo
Note: that\'s a long read, but I explained the whole thinking process. It\'s going to be worth it if you want to learn and not to memorize solutions :)\n\nIf you found it helpful, please upvote <3\n\n<hr />\n\n\nLet\'s start with the basics\n\nFirst, how do we generate the coordinates for all the submatrices? we need all distinct (x1,y1), (x2,y2) pairs\n\nSo it will be something like this:\n\n```\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m, n = len(matrix), len(matrix[0])\n        # Generate all submatrices\n        for y1 in range(m):\n            for x1 in range(n):\n                for y2 in range(y1, m):\n                    for x2 in range(x1, n):\n                        print(f"({x1}, {y1}), ({x2, y2})")\n```\n\n\nAnd a brute force would be to count the sum between all pairs of coordinates\n\n```\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m, n = len(matrix), len(matrix[0])\n        ans = 0\n        \n        # Generate all submatrices\n        for y1 in range(m):\n            for x1 in range(n):\n                for y2 in range(y1, m):\n                    for x2 in range(x1, n):\n                        # We could sum the distance between the coordinates\n                        total = 0\n                        for r in range(y1, y2+1):\n                            for c in range(x1, x2+1):\n                                total += matrix[r][c]\n                \n                        if total == target:\n                            ans += 1\n        return ans\n```\n\n\nObviously that\'s too bad of a solution with `n^3*m^3`\n\n# Improvement\n\nIn the last example, we had to iterate from (x1,y1) to (x2,y2) to find the sum.\n\nWe can reduce the time complexity for finding the sum to `O(1)` instead of `O(m*n)`, but how?\n\nBy using `prefix sums` (or prefix matrices one may say), extending the idea of a prefix sum array\n\nLet\'s look at the image below:\n\n\n**UPDATE**: **the value 8 is calculated as `7+6+(-3)-2`. The image has a mistake in it.. Sorry \nAll other calculations are fine**\n**Also the usage of DP in the image is for convenience, it\'s not a dynamic programming question.**\n\n![image](https://assets.leetcode.com/users/images/5de8eaf9-89e4-4dd9-afde-6317934c0aeb_1658129118.454311.png)\n\nEvery coordinate (x,y) is the matrix sum between origin `(0,0) and (x,y)`\n\nWe can calculate the sum by taking the sum of the matrix above `matrix_sum[row-1][col]`, adding the sum of the matrix behind `matrix_sum[row][col-1]` and removing the intersection, because there is a part that is added twice `matrix_sum[row-1][col-1]`\n\nThen to calculate the sum of some `submatrix (x1,y1), (x2,y2)` we need to add the sum of the matrix that ends at the bottom coordinates, and remove the parts which are unused (again there is an intersection, hence we need to add the intersection because it\'s removed twice)\n\n![image](https://assets.leetcode.com/users/images/4dbde7d6-b63f-428c-a8bd-467c5f97b330_1658129404.9013832.png)\n\n\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m, n = len(matrix), len(matrix[0])\n        matrix_sums = [[0 for _ in range(n)] for _ in range(m)]\n        \n        # Calculate all the submatrices sum with the transition formula we found\n        for row in range(m):\n            for col in range(n):\n                # first cell\n                if row == 0 and col == 0:\n                    matrix_sums[row][col] = matrix[row][col]\n                # Rows and columns are like prefix sums, without intersection\n                elif row == 0:\n                    matrix_sums[row][col] = matrix[row][col] + matrix_sums[row][col-1]\n                elif col == 0:\n                    matrix_sums[row][col] = matrix[row][col] + matrix_sums[row-1][col]\n                \n                # current sum is the sum of the matrix above, to the left and subtract the intersection\n                else:\n                    matrix_sums[row][col] = matrix[row][col] \\\n                    + (matrix_sums[row][col-1]) \\\n                    + (matrix_sums[row-1][col]) \\\n                    - (matrix_sums[row-1][col-1])\n\n                \n        ans = 0\n        # Generate all submatrices\n        for y1 in range(m):\n            for x1 in range(n):\n                for y2 in range(y1, m):\n                    for x2 in range(x1, n):\n                        # calculate sum in O(1)\n                        submatrix_total = matrix_sums[y2][x2] \\\n                        - (matrix_sums[y2][x1-1] if x1-1 >= 0 else 0) \\\n                        - (matrix_sums[y1-1][x2] if y1-1 >= 0 else 0) \\\n                        + (matrix_sums[y1-1][x1-1] if y1-1 >= 0 and x1-1 >= 0 else 0)\n                        \n                        if submatrix_total == target:\n                            ans += 1\n        return ans\n```\n\n# Do we really need 2 separate iterations?\nWe can inverse the order of iterations, to build the prefix matrix and calculate in one go\n\n```\nclass Solution:\n    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:\n        m, n = len(matrix), len(matrix[0])\n        matrix_sums = [[0 for _ in range(n)] for _ in range(m)]\n        \n        ans = 0\n        # Generate all submatrices\n        for y1 in range(m):\n            for x1 in range(n):\n                # Calculate matrix_sums\n                # first cell\n                if y1 == 0 and x1 == 0:\n                    matrix_sums[y1][x1] = matrix[y1][x1]\n                # Rows and columns are like prefix sums, without intersection\n                elif y1 == 0:\n                    matrix_sums[y1][x1] = matrix[y1][x1] + matrix_sums[y1][x1-1]\n                elif x1 == 0:\n                    matrix_sums[y1][x1] = matrix[y1][x1] + matrix_sums[y1-1][x1]\n                \n                # current sum is the sum of the matrix above, to the left and subtract the intersection\n                else:\n                    matrix_sums[y1][x1] = matrix[y1][x1] \\\n                    + (matrix_sums[y1][x1-1]) \\\n                    + (matrix_sums[y1-1][x1]) \\\n                    - (matrix_sums[y1-1][x1-1])\n                \n                for y2 in range(y1 + 1):\n                    for x2 in range(x1 + 1):\n                        submatrix_total = matrix_sums[y1][x1] \\\n                        - (matrix_sums[y1][x2-1] if x2-1 >= 0 else 0) \\\n                        - (matrix_sums[y2-1][x1] if y2-1 >= 0 else 0) \\\n                        + (matrix_sums[y2-1][x2-1] if y2-1 >= 0 and x2-1 >= 0 else 0)\n                        \n                        if submatrix_total == target:\n                            ans += 1\n        return ans\n```\n\n\n# But wait...\nWe can optimize even more!\n\nWe have time complexity of `m^2*n^2` but do we really need the `n^2` ?\n\nInstead, it\'s enough to simply "fix" the vertical coordinates y1, y2 and let x iterate\n\nThis way, we can reduce the problem into **subarray sum equal to target** (1D problem)\n\nFinal complexity: `O(m^2*n)`\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        matrix_sums = [[0 for _ in range(n)] for _ in range(m)]\n        \n        # Calculate all the submatrices sum with the transition formula we found\n        for row in range(m):\n            for col in range(n):\n                # first cell\n                if row == 0 and col == 0:\n                    matrix_sums[row][col] = matrix[row][col]\n                # Rows and columns are like prefix sums, without intersection\n                elif row == 0:\n                    matrix_sums[row][col] = matrix[row][col] + matrix_sums[row][col-1]\n                elif col == 0:\n                    matrix_sums[row][col] = matrix[row][col] + matrix_sums[row-1][col]\n                \n                # current sum is the sum of the matrix above, to the left and subtract the intersection\n                else:\n                    matrix_sums[row][col] = matrix[row][col] \\\n                    + (matrix_sums[row][col-1]) \\\n                    + (matrix_sums[row-1][col]) \\\n                    - (matrix_sums[row-1][col-1])\n\n                \n        ans = 0\n        for y1 in range(m):\n            for y2 in range(y1, m):\n                # Reduce the problem to subarray sum of target\n                subarray_sums = defaultdict(int)\n                subarray_sums[0] = 1\n                \n                for x in range(n):\n                    matrix_sum = matrix_sums[y2][x]\n                    \n                    # Remove to matrix sum above y1\n                    if y1 > 0:\n                        matrix_sum -= matrix_sums[y1-1][x]\n                        \n                    if matrix_sum - target in subarray_sums:\n                        ans += subarray_sums[matrix_sum - target]\n                    \n                    subarray_sums[matrix_sum] += 1\n        return ans\n```
['Python']