LeetCode [1314] Matrix Block Sum

 1314. Matrix Block Sum

Medium

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

 

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n, K <= 100
• 1 <= mat[i][j] <= 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public int[][] matrixBlockSum(int[][] mat, int K) { int m = mat.length, n = mat[0].length; int[][] sum = new int[m+1][n+1]; for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i-1][j-1]; } } int[][] ret = new int[m][n]; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ int i1 = Math.max(0, i-K)+1; int j1 = Math.max(0, j-K)+1; int i2 = Math.min(m-1, i+K)+1; int j2 = Math.min(n-1, j+K)+1; ret[i][j] = sum[i2][j2]-sum[i1-1][j2]-sum[i2][j1-1]+sum[i1-1][j1-1]; } } return ret; } }