2D Prefix Sum Problem
Approach\n Describe your approach to solving the problem. \n1. Compute 2D prefix sum\n2. Reduce to 1D subarray problem\n\n# Complexity\n- Time complexity: O(mmn
# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Compute 2D prefix sum\n2. Reduce to 1D subarray problem\n\n# Complexity\n- Time complexity: O(mmn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n\n# Code\n```\nclass Solution {\n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        int m = matrix.length;\n        int n = matrix[0].length;\n\n        // step1 : calculate 2d prefix sum\n        int[][] preSum = new int[m+1][n+1];\n        for (int i = 1; i <= m;i++) {\n\t\t    for (int j = 1;j <= n;j++){\n\t\t\t\tpreSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1];\n\t\t    }\n        }\n\n        Map<Integer, Integer> map = new HashMap<>();\n        int count = 0;\n        // step2: reduce this 2d problem to 1d\n        for (int i = 1; i <= m; i++) {\n            for (int j = i; j <= m; j++) {\n                // consider every fixed row pair, so we need a new map each time\n                // treat it a 1d array since the row is fixed, the only var is column\n                map.clear();\n                map.put(0, 1);\n                for (int k = 1; k <= n; k++) {\n                    // current prefix sum\n                    int curSum = preSum[j][k] - preSum[i - 1][k];\n\n                    // subarray which sums up to (curSum - target)\n                    count += map.getOrDefault(curSum - target, 0);\n\n                    // add current sum into map\n                    map.put(curSum, map.getOrDefault(curSum, 0) + 1);\n                }\n            }\n        }\n    return count;\n    }\n}\n```
['Java']