Description#
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.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution:
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
m, n = len(mat), len(mat[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
pre[i][j] = (
pre[i - 1][j]
+ pre[i][j - 1]
- pre[i - 1][j - 1]
+ mat[i - 1][j - 1]
)
def get(i, j):
i = max(min(m, i), 0)
j = max(min(n, j), 0)
return pre[i][j]
ans = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
ans[i][j] = (
get(i + k + 1, j + k + 1)
- get(i + k + 1, j - k)
- get(i - k, j + k + 1)
+ get(i - k, j - k)
)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
private int[][] pre;
private int m;
private int n;
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
int[][] pre = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; ++i) {
for (int j = 1; j < n + 1; ++j) {
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + -pre[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
this.pre = pre;
this.m = m;
this.n = n;
int[][] ans = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans[i][j] = get(i + k + 1, j + k + 1) - get(i + k + 1, j - k)
- get(i - k, j + k + 1) + get(i - k, j - k);
}
}
return ans;
}
private int get(int i, int j) {
i = Math.max(Math.min(m, i), 0);
j = Math.max(Math.min(n, j), 0);
return pre[i][j];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
for (int i = 1; i < m + 1; ++i) {
for (int j = 1; j < n + 1; ++j) {
pre[i][j] = pre[i - 1][j] + pre[i][j - 1] + -pre[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
vector<vector<int>> ans(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans[i][j] = get(i + k + 1, j + k + 1, m, n, pre) - get(i + k + 1, j - k, m, n, pre) - get(i - k, j + k + 1, m, n, pre) + get(i - k, j - k, m, n, pre);
}
}
return ans;
}
int get(int i, int j, int m, int n, vector<vector<int>>& pre) {
i = max(min(m, i), 0);
j = max(min(n, j), 0);
return pre[i][j];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func matrixBlockSum(mat [][]int, k int) [][]int {
m, n := len(mat), len(mat[0])
pre := make([][]int, m+1)
for i := 0; i < m+1; i++ {
pre[i] = make([]int, n+1)
}
for i := 1; i < m+1; i++ {
for j := 1; j < n+1; j++ {
pre[i][j] = pre[i-1][j] + pre[i][j-1] + -pre[i-1][j-1] + mat[i-1][j-1]
}
}
get := func(i, j int) int {
i = max(min(m, i), 0)
j = max(min(n, j), 0)
return pre[i][j]
}
ans := make([][]int, m)
for i := 0; i < m; i++ {
ans[i] = make([]int, n)
for j := 0; j < n; j++ {
ans[i][j] = get(i+k+1, j+k+1) - get(i+k+1, j-k) - get(i-k, j+k+1) + get(i-k, j-k)
}
}
return ans
}
|
