@@ -38,4 +38,43 @@ private List<Integer> findRange(int iOrJ, int k, int upper) {
3838 return range ;
3939 }
4040 }
41+
42+ public static class Solution2 {
43+ /**
44+ * This is using prefix sum, much more efficient and saves a lot of repeated computation,
45+ * built on top of this: https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_304.java
46+ */
47+ public int [][] matrixBlockSum (int [][] mat , int k ) {
48+ int m = mat .length ;
49+ int n = mat [0 ].length ;
50+ int [][] prefixSum = new int [m + 1 ][n + 1 ];
51+ for (int i = 0 ; i < m ; i ++) {
52+ for (int j = 0 ; j < n ; j ++) {
53+ //because we add prefixSum[i + 1][j] and prefixSum[i][j + 1], this means we added their shared area twice, so we'll deduct it once: prefixSum[i][j]
54+ prefixSum [i + 1 ][j + 1 ] = mat [i ][j ] + prefixSum [i + 1 ][j ] + prefixSum [i ][j + 1 ] - prefixSum [i ][j ];
55+ }
56+ }
57+ int [][] result = new int [m ][n ];
58+ for (int i = 0 ; i < m ; i ++) {
59+ for (int j = 0 ; j < n ; j ++) {
60+ int [] range = findRange (i , j , k , m , n );
61+ int row1 = range [0 ];
62+ int col1 = range [2 ];
63+ int row2 = range [1 ];
64+ int col2 = range [3 ];
65+ //because we deducted prefixSum[row2 + 1][col1] and prefixSum[row1][col2 + 1], we deducted the shared area prefixSum[row1][col1] twice, so we added it back
66+ result [i ][j ] = prefixSum [row2 + 1 ][col2 + 1 ] - prefixSum [row2 + 1 ][col1 ] - prefixSum [row1 ][col2 + 1 ] + prefixSum [row1 ][col1 ];
67+ }
68+ }
69+ return result ;
70+ }
71+
72+ private int [] findRange (int i , int j , int k , int m , int n ) {
73+ int rowMin = i - k < 0 ? 0 : i - k ;
74+ int rowMax = i + k < m ? i + k : m - 1 ;
75+ int colMin = j - k < 0 ? 0 : j - k ;
76+ int colMax = j + k < n ? j + k : n - 1 ;
77+ return new int []{rowMin , rowMax , colMin , colMax };
78+ }
79+ }
4180}
0 commit comments