_1314.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.List;

publicclass_1314 {
publicstaticclassSolution1 {
/*
 * This is a brute force solution without using prefix sum. i.e. lots of repeated computation.
 */
publicint[][] matrixBlockSum(int[][] mat, intk) {
intm = mat.length;
intn = mat[0].length;
int[][] answer = newint[m][n];
for (inti = 0; i < m; i++) {
for (intj = 0; j < n; j++) {
List<Integer> iRange = findRange(i, k, m);
List<Integer> jRange = findRange(j, k, n);
intsum = 0;
for (intii = 0; ii < iRange.size(); ii++) {
for (intjj = 0; jj < jRange.size(); jj++) {
sum += mat[iRange.get(ii)][jRange.get(jj)];
 }
 }
answer[i][j] = sum;
 }
 }
returnanswer;
 }

privateList<Integer> findRange(intiOrJ, intk, intupper) {
intmin = (iOrJ - k) < 0 ? 0 : (iOrJ - k);
intmax = (iOrJ + k) >= upper ? (upper - 1) : (iOrJ + k);
List<Integer> range = newArrayList<>();
for (inti = min; i <= max; i++) {
range.add(i);
 }
returnrange;
 }
 }

publicstaticclassSolution2 {
/*
 * This is using prefix sum, much more efficient and saves a lot of repeated computation,
 * built on top of this: https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_304.java
 */
publicint[][] matrixBlockSum(int[][] mat, intk) {
intm = mat.length;
intn = mat[0].length;
int[][] prefixSum = newint[m + 1][n + 1];
for (inti = 0; i < m; i++) {
for (intj = 0; j < n; j++) {
// 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]
prefixSum[i + 1][j + 1] =
mat[i][j] + prefixSum[i + 1][j] + prefixSum[i][j + 1] - prefixSum[i][j];
 }
 }
int[][] result = newint[m][n];
for (inti = 0; i < m; i++) {
for (intj = 0; j < n; j++) {
int[] range = findRange(i, j, k, m, n);
introw1 = range[0];
intcol1 = range[2];
introw2 = range[1];
intcol2 = range[3];
// 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
result[i][j] =
prefixSum[row2 + 1][col2 + 1]
 - prefixSum[row2 + 1][col1]
 - prefixSum[row1][col2 + 1]
 + prefixSum[row1][col1];
 }
 }
returnresult;
 }

privateint[] findRange(inti, intj, intk, intm, intn) {
introwMin = i - k < 0 ? 0 : i - k;
introwMax = i + k < m ? i + k : m - 1;
intcolMin = j - k < 0 ? 0 : j - k;
intcolMax = j + k < n ? j + k : n - 1;
returnnewint[] {rowMin, rowMax, colMin, colMax};
 }
 }
}