Number of Submatrices That Sum to Target | JS, Python, Java, C++ | Short Solution w/ Explanation
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nThis problem is essentially a **2-dimensional** version of [**#560. Subarray Sum Equals K (S.S.E.K)**](https://leetcode.com/problems/subarray-sum-equals-k/description/). By using a **prefix sum** on each row or each column, we can compress this problem down to either **N^2** iterations of the **O(M)** SSEK, or **M^2** iterations of the **O(N)** SSEK.\n\nIn the SSEK solution, we can find the number of subarrays with the target sum by utilizing a **result map** (**res**) to store the different values found as we iterate through the array while keeping a running sum (**csum**). Just as in the case with a prefix sum array, the sum of a subarray between **i** and **j** is equal to the sum of the subarray from **0** to **j** minus the sum of the subarray from **0** to **i-1**.\n\nRather than iteratively checking if **sum[0,j] - sum[0,i-1] = T** for every pair of **i, j** values, we can flip it around to **sum[0,j] - T = sum[0,i-1]** and since every earlier sum value has been stored in **res**, we can simply perform a lookup on **sum[0,j] - T** to see if there are any matches.\n\nWhen extrapolating this solution to our **2-dimensional** matrix (**M**), we will need to first prefix sum the rows or columns, (which we can do **in-place** to avoid extra space, as we will not need the original values again). Then we should iterate through **M** again in the opposite order of rows/columns where the prefix sums will allow us to treat a group of columns or rows as if it were a **1-dimensional** array and apply the SSEK algorithm.\n\n---\n\n#### ***Implementation:***\n\nPython, oddly, has _much_ better performance with the use of a simple **dict** instead of a **defaultdict** for **res** (Thanks, [@slcheungcasado](https://leetcode.com/slcheungcasado)!)\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **232ms / 44.8MB** (beats 100% / 81%).\n```javascript\nvar numSubmatrixSumTarget = function(M, T) {\n    let xlen = M[0].length, ylen = M.length,\n        ans = 0, res = new Map(), csum\n    for (let i = 0, r = M[0]; i < ylen; r = M[++i]) \n        for (let j = 1; j < xlen; j++)\n            r[j] += r[j-1]\n    for (let j = 0; j < xlen; j++)\n        for (let k = j; k < xlen; k++) {\n            res.clear(), res.set(0,1), csum = 0\n            for (let i = 0; i < ylen; i++) {\n                csum += M[i][k] - (j ? M[i][j-1] : 0)\n                ans += (res.get(csum - T) || 0)\n                res.set(csum, (res.get(csum) || 0) + 1)\n            }\n        }\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **552ms / 15.0MB** (beats 100% / 85%).\n```python\nclass Solution:\n    def numSubmatrixSumTarget(self, M: List[List[int]], T: int) -> int:\n        xlen, ylen, ans = len(M[0]), len(M), 0\n        for r in M:\n            for j in range(1, xlen):\n                r[j] += r[j-1]\n        for j in range(xlen):\n            for k in range(j, xlen):\n                res, csum = {0: 1}, 0\n                for r in M:\n                    csum += r[k] - (r[j-1] if j else 0)\n                    if csum - T in res: ans += res[csum-T]\n                    res[csum] = res[csum] + 1 if csum in res else 1  \n        return ans\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **81ms / 39.3MB** (beats 96% / 95%).\n```java\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] M, int T) {\n        int xlen = M[0].length, ylen = M.length, ans = 0;\n        Map<Integer, Integer> res = new HashMap<>();\n        for (int[] r : M)\n            for (int j = 1; j < xlen; j++)\n                r[j] += r[j-1];\n        for (int j = 0; j < xlen; j++)\n            for (int k = j; k < xlen; k++) {\n                res.clear();\n                res.put(0,1);\n                int csum = 0;\n                for (int i = 0; i < ylen; i++) {\n                    csum += M[i][k] - (j > 0 ? M[i][j-1] : 0);\n                    ans += res.getOrDefault(csum - T, 0);\n                    res.put(csum, res.getOrDefault(csum, 0) + 1);\n                }\n            }\n        return ans;\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **484ms / 95.3MB** (beats 96% / 76%).\n```c++\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& M, int T) {\n        int xlen = M[0].size(), ylen = M.size(), ans = 0;\n        unordered_map<int, int> res;\n        for (int i = 0; i < ylen; i++)\n            for (int j = 1; j < xlen; j++)\n                M[i][j] += M[i][j-1];\n        for (int j = 0; j < xlen; j++)\n            for (int k = j; k < xlen; k++) {\n                res.clear();\n                res[0] = 1;\n                int csum = 0;\n                for (int i = 0; i < ylen; i++) {\n                    csum += M[i][k] - (j ? M[i][j-1] : 0);\n                    ans += res.find(csum - T) != res.end() ? res[csum - T] : 0;\n                    res[csum]++;\n                }\n            }\n        return ans;\n    }\n};\n```
[]