Given a m x 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 &lt;= r &lt;= i + k,
	j - k &lt;= c &lt;= j + k, and
	(r, c) is a valid position in the matrix.


&nbsp;
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]]


&nbsp;
Constraints:


	m ==&nbsp;mat.length
	n ==&nbsp;mat[i].length
	1 &lt;= m, n, k &lt;= 100
	1 &lt;= mat[i][j] &lt;= 100


class Solution:
    def matrixBlockSum(self, matrix: List[List[int]], k: int) -> List[List[int]]:
        ROWS, COLS = len(matrix), len(matrix[0])

        prefix_sums = [[0] * (COLS + 1) for _ in range(ROWS + 1)]

        for r in range(1, ROWS + 1):
            for c in range(1, COLS + 1):
                prefix_sums[r][c] = prefix_sums[r - 1][c] + prefix_sums[r][c - 1] + \
                    matrix[r - 1][c - 1] - prefix_sums[r - 1][c - 1]

        res = [[0] * COLS for _ in range(ROWS)]
        for r in range(ROWS):
            for c in range(COLS):
                res[r][c] = prefix_sums[min(r + k + 1, ROWS)][min(c + k + 1, COLS)] - \
                    prefix_sums[max(r - k, 0)][min(c + k + 1, COLS)] - \
                    prefix_sums[min(r + k + 1, ROWS)][max(c - k, 0)] + \
                    prefix_sums[max(r - k, 0)][max(c - k, 0)]

        return res
class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length,n = mat[0].length;
        int[][] answer = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int val = 0;
                // take new variables to get starting index of mat[r][c]
                int p = i-k,q=j-k;
                //make sure p and q are atleast 0 (i.e. valid)
                while(p<0)
                    p++;
                while(q<0)
                    q++;
                //traverse again in the matrix with starting at p,q and ending at i+k and j+k
                //add conditions to make sure the indices dont cross the values of m and n
                for(int x = p;x<=i+k && x<m;x++){
                    for(int y = q;y<=j+k && y<n;y++){
                        val += mat[x][y];
                    }
                }
                answer[i][j] = val;
            }
        }
        return answer;
    }
}
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> pref(n+1, vector<int>(m+1, 0));
        // Calculating prefix sum
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                // note that while counting for [i-1][j] and [i][j-1];
                // pref[i-1][j-1] will be added twice. So we reduce it once.
                pref[i][j] = mat[i-1][j-1] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
            }
        }

        // Find the sum of the elements specified in the K-block
        vector<vector<int>> res(n, vector<int>(m, 0));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // checking for all pairs to be in bounds.
                int r1 = max(0, i-k);
                int c1 = max(0, j-k);
                int r2 = min(n-1, i+k);
                int c2 = min(m-1, j+k);
                // finding res[i][j] = bottom right - bottom left - top right + top left
                res[i][j] = pref[r2+1][c2+1] - pref[r2+1][c1] - pref[r1][c2+1] + pref[r1][c1];
            }
        }

        return res;

    }
};
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[][]}
 */
var matrixBlockSum = function(mat, k) {
    let sum = 0;
    let dp = Array(mat.length + 1);
    dp[0] = Array(mat[0].length).fill(0);

    // sum of row el
    for (let i = 0; i < mat.length; i++){
        dp[i + 1] = Array(mat[0].length).fill(0);
        for (let j = 0; j < mat[0].length; j++){
            dp[i + 1][j] += mat[i][j] + sum;
            sum = dp[i + 1][j];
        }
        sum = 0;
    }

    // sum of col el
    for (let j = 0; j < mat[0].length; j++){
        for (let i = 0; i < mat.length; i++){
            dp[i + 1][j] += sum;
            sum = dp[i + 1][j];
        }
        sum = 0;
    }

    dp = dp.slice(1);

    // cal sum of blocks
    for (let i = 0; i < mat.length; i++){
        let r1 = Math.max(0, i - k);
        let r2 = Math.min(mat.length - 1, i + k);
        for (let j = 0; j < mat[0].length; j++){
            let c1 = Math.max(0, j - k);
            let c2 = Math.min(mat[0].length - 1, j + k);

            let value = dp[r2][c2];

            if (r1 - 1 >= 0){
                value -= dp[r1 - 1][c2];
            }
            if (c1 - 1 >= 0){
                value -= dp[r2][c1 - 1]
            }
            if (r1 - 1 >= 0 && c1 - 1 >= 0){
                value += dp[r1 - 1][c1 - 1];
            }
            mat[i][j] = value;
        }
    }

    return mat;

};
Matrix Block Sum