Vertical And Horizontal Prefix Sum | Java | C++
Intuition, approach, and complexity discussed in video solution in detail.\nhttps://youtu.be/otmammzWYgI\n\n# Code\nJava\n\nclass Solution {\n    public int num
# Intuition, approach, and complexity discussed in video solution in detail.\nhttps://youtu.be/otmammzWYgI\n\n# Code\nJava\n```\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int rows = matrix.length, cols = matrix[0].length;\n        \n        for(int[] row : matrix){\n            for(int col = 1; col < cols; col++){\n                row[col] += row[col-1];\n            }\n        }\n        \n        int sumCnt = 0;\n        \n        for(int left = 0; left < cols; left++){\n            for(int right = left; right < cols; right++){\n                int currPrefSum = 0;\n                Map<Integer, Integer> sumFreq = new HashMap<>();\n                sumFreq.put(0, 1);\n                \n                for(int r = 0; r < rows; r++){\n                    int prefSumCurrRow = matrix[r][right] - ((left - 1 > -1) ? matrix[r][left - 1] : 0);\n                    currPrefSum += prefSumCurrRow;\n                    if(sumFreq.containsKey(currPrefSum - target)){\n                        sumCnt += sumFreq.get(currPrefSum - target);\n                    }\n                    sumFreq.put(currPrefSum, sumFreq.getOrDefault(currPrefSum, 0) + 1);\n                }\n            }\n        }\n        return sumCnt;\n    }\n}\n\n\n```\nC++\n```\nclass Solution {\nprivate:\n     void printMat(vector<vector<int>> mat){\n         for(auto &row : mat){\n             for(auto val : row){\n                 cout<<val<<" ";\n             }\n             cout<<endl;\n         }\n         cout<<endl;\n     }    \npublic:\n    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {\n        int rows = matrix.size(), cols = matrix[0].size();\n        for(auto &row : matrix){\n            for(int col = 1; col < cols; col++){\n                row[col] += row[col-1];\n            }\n        }\n        int sumCnt = 0;\n        for(int left = 0; left < cols; left++){\n            for(int right = left; right < cols; right++){\n                int currPrefSum = 0;\n                unordered_map<int, int> sumFreq;\n                sumFreq[0]++;\n                for(int r = 0; r < rows; r++){\n                    int prefSumCurrRow = matrix[r][right] - ((left - 1 > -1) ? matrix[r][left - 1] : 0);\n                    currPrefSum += prefSumCurrRow;\n                    if(sumFreq.count(currPrefSum-target)){\n                        sumCnt += sumFreq[currPrefSum-target];\n                    }\n                    sumFreq[currPrefSum]++;\n                }\n            }\n        }\n        return sumCnt;\n    }\n};\n```
['Prefix Sum', 'C++', 'Java']