C++ Java Python || Subarray Sum || Explained
Plz Upvote if found helpful\n\nExplaination:\nThis problem is essentially a 2-dimensional version of #560. Subarray Sum Equals K (S.S.E.K). By using a prefix su
**Plz Upvote if found helpful**\n\n**Explaination:**\nThis problem is essentially a 2-dimensional version of #560. Subarray Sum Equals K (S.S.E.K). 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**C++  Code**\n```\nclass Solution {\npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int rows = matrix.size() , cols = matrix[0].size();\n        \n        if(rows < 1){\n            return 0;\n        }\n        \n        // calculate prefix sum for rows\n        for(int row = 0 ; row < rows ; row++){\n            for(int col = 1 ; col < cols ;col++){\n                matrix[row][col] =  matrix[row][col] + matrix[row][col -1];\n            }\n        }\n      \n        int count = 0 , sum ;\n        unordered_map<int , int> counter;\n        for(int colstart = 0 ; colstart < cols ;colstart++){\n            for(int col = colstart ; col < cols; col++){\n                counter.clear();\n                counter[0] = 1;\n                sum =0;\n                for(int row = 0 ; row < rows ;row++){\n                    sum += matrix[row][col] - (colstart > 0 ? matrix[row][colstart - 1] : 0 );\n                    count += (counter.find(sum- target) != counter.end() ? counter[sum-target] : 0);\n                    counter[sum]++;\n                }\n            }\n        }\n        return count;\n    }\n};\n```\n\n**Java Code:**\n```\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**Python Code**\n```\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**Please Upvote if found Helpful**
['C', 'Python', 'Java']