# 1314. Matrix Block Sum

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 <= 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`

``````class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> sums(m + 1, vector<int>(n + 1)), res(m, vector<int>(n));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sums[i][j] = mat[i - 1][j - 1] + sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1];
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x = min(m - 1, i + k), y = min(n - 1, j + k);
int p = max(0, i - k), q = max(0, j - k);
res[i][j] = sums[x + 1][y + 1] - sums[x + 1][q] - sums[p][y + 1] + sums[p][q];
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1314

Stamping the Grid

https://leetcode.com/problems/matrix-block-sum/

https://leetcode.com/problems/matrix-block-sum/discuss/500833/C%2B%2B-prefix-sum-with-explanation

https://leetcode.com/problems/matrix-block-sum/discuss/477041/Java-Prefix-sum-with-Picture-explain-Clean-code-O(m*n)

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation