[Java] ✨✨✨ Prefix sum 2D, explained with pictures
Intuition\nWe need to have a quick way to understand what is the sum for the given matrix. We can start from prefix sum 2D (in matrix), where each element (i, j
# Intuition\nWe need to have a quick way to understand what is the sum for the given matrix. We can start from **prefix sum 2D** (in matrix), where each element (i, j) will hold sum for all elements in matrix for x from 0 to i, and y from 0 to j.\n\nPrefix sum matrix will be calculated in a loop using result of previous elements:\n![image](https://live.staticflickr.com/65535/53492870323_1f0819695b_n.jpg)\n\nSo we will use formula:\n$$Sum(i, j) = matrix(i, j) + sum(i, j-1) + sum(i-1, j) - sum(i-1, j-1)$$\nWe are subtracting sum(i-1,j-1) because it\'s counted twice from (i, j-1) and (i-1, j).\n\nBased on this results we can calculate sum for **any** matrix, not necessarily starting from x=0 and y=0:\n![image](https://live.staticflickr.com/65535/53493036004_61fdd3f1e9.jpg)\ni.e.:\n$$sum(x1,y1,x2,y2) = sum(x2,y2) - sum(x2,y1-1) - sum(x1-1, y2) + sum (x1-1,y1-1)$$\n\nIn case if x1-1 or y1-1 become negative - we just use 0 instead of matrix value.\n\n# Approach\n1) Calculate matrix prefix sum 2D array - see above approach.\n2) Fix y1 = 0 - it will be always 0 in our solution (i.e. we will always start from 1st column).\n3) For each x1 fix x2 values one by one (i.e. we fix set of rows, e.g. 0,1, then 0,1,2, then 0,1,2,3, etc., and same for other x1, e.g. 2,3,4 -> 2,3,4,5, etc.). Main calculations will happen then for fixed x1, x2, y1;\n4) Define Map<Integer, Integer> - it will store number of occurrencies of any specific sum. Init count = 0;\n5) Iterate y2 from 0 to n-1. \nFor each y2:\n- calculate matrix sum - see intution 2nd picture and formula;\n- if sum == target, then increment count by 1 (we found matrix resulting in target).\n- Add to count the number of occurencies so far of the **sum - target** values. Why do we do this? Let\'s imagine we fixed x1, x2, y1, and increment y2 from 0 to n-1. Let\'s assume target = 3. We get sums: 0, 4, 5, 7, 8, 9. So far no sums = target = 3. Let\'s look at sums 4 and 7. If we decrement 4 from 7 - we will get 3. It means if we take y1 = 2 and y2 = 3 - we will get sum equal not to 7, but to 7-4=3 (as we removed left part of the matrix). That\'s basically how prefix sum works. Same for 5 vs 8 - for y1 = 3 and y2 = 4 we would get sum=3, unlike 8 that we\'re getting for y1 = 0.\n- Add current sum to the map for the next iterations.\n6) Clean prefix map on each changing x1 and x2 - we will start from a scratch for different boundaries.\n7) After all iterations return count.\n\n# Complexity\nM - number of rows;\nN - number of columns;\n\n- Time complexity:\n$$O(N*M^2)$$\n\n- Space complexity:\n$$O(M*N)$$\n\n# Code\n```\nclass Solution {\n\n    private int m;\n    private int n;\n    \n    public int numSubmatrixSumTarget(int[][] matrix, int target) {\n        m = matrix.length;\n        n = matrix[0].length;\n        int[][] sumMatrix = prepareSumMatrix(matrix);\n        int count = 0;\n        Map<Integer, Integer> countsMap = new HashMap<>();\n        for (int x1 = 0; x1 < m; x1++) {\n            countsMap.clear();\n            for (int k1 = 0; x1 + k1 < m; k1++) {\n                int x2 = x1 + k1;\n                countsMap.clear();\n                for (int y2 = 0; y2 < n; y2++) {\n                    int currSum = matrixSumFor(sumMatrix, x1, 0, x2, y2);\n                    if (currSum == target) {                        \n                        count++;\n                    }\n                    count += countsMap.getOrDefault(currSum - target, 0);\n                    countsMap.put(currSum, countsMap.getOrDefault(currSum, 0) + 1);\n                }\n            }\n        }\n        return count;\n    }\n\n    private int matrixSumFor(int[][] sumMatrix, int x1, int y1, int x2, int y2) {\n        return sumMatrix[x2][y2] - (x1 == 0? 0 : sumMatrix[x1 - 1][y2]) - (y1 == 0? 0 : sumMatrix[x2][y1-1]) \n            + (x1 == 0 || y1 == 0 ? 0 : sumMatrix[x1-1][y1-1]);\n    }\n\n    private int[][] prepareSumMatrix(int[][] matrix) {\n        int[][] sum = new int[m][n];\n        sum[0][0] = matrix[0][0];\n        for (int i = 1; i < m; i++) {\n            sum[i][0] = sum[i-1][0] + matrix[i][0];\n        }\n        for (int j = 1; j < n; j++) {\n            sum[0][j] = sum[0][j-1] + matrix[0][j];\n        }\n        for (int i = 1; i < m; i++) {\n            for (int j = 1; j < n; j++) {\n                sum[i][j] = matrix[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];\n            }\n        }\n        return sum;\n    }\n}\n```
['Java']