Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1314.html
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.lengthn == mat[i].length1 <= m, n, K <= 1001 <= mat[i][j] <= 100
Related Topics:
Dynamic Programming
Solution 1.
// OJ: https://leetcode.com/problems/matrix-block-sum/
// Time: O(MN)
// Space: O(1)
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& A, int K) {
int M = A.size(), N = A[0].size();
for (int i = 0; i < M; ++i) {
int sum = 0;
for (int j = 0; j < N; ++j) {
sum += A[i][j];
A[i][j] = sum + (i - 1 >= 0 ? A[i - 1][j] : 0);
}
}
vector<vector<int>> ans(M, vector<int>(N));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
int minr = max(-1, i - K - 1), maxr = min(M - 1, i + K), minc = max(-1, j - K - 1), maxc = min(N - 1, j + K);
int a = A[maxr][maxc], b = minc == -1 ? 0 : A[maxr][minc], c = minr == -1 ? 0 : A[minr][maxc], d = minr == -1 || minc == -1 ? 0 : A[minr][minc];
ans[i][j] = a - b - c + d;
}
}
return ans;
}
};
-
class Solution { public int[][] matrixBlockSum(int[][] mat, int K) { int rows = mat.length, columns = mat[0].length; int[][] sums = new int[rows][columns]; for (int i = 0; i < rows; i++) { int minRow = Math.max(i - K, 0); int maxRow = Math.min(i + K, rows - 1); for (int j = 0; j < columns; j++) { int minColumn = Math.max(j - K, 0); int maxColumn = Math.min(j + K, columns - 1); for (int r = minRow; r <= maxRow; r++) { for (int c = minColumn; c <= maxColumn; c++) sums[i][j] += mat[r][c]; } } } return sums; } } ############ 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]; } } -
// OJ: https://leetcode.com/problems/matrix-block-sum/ // Time: O(MN) // Space: O(1) class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& A, int K) { int M = A.size(), N = A[0].size(); for (int i = 0; i < M; ++i) { int sum = 0; for (int j = 0; j < N; ++j) { sum += A[i][j]; A[i][j] = sum + (i - 1 >= 0 ? A[i - 1][j] : 0); } } vector<vector<int>> ans(M, vector<int>(N)); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { int minr = max(-1, i - K - 1), maxr = min(M - 1, i + K), minc = max(-1, j - K - 1), maxc = min(N - 1, j + K); int a = A[maxr][maxc], b = minc == -1 ? 0 : A[maxr][minc], c = minr == -1 ? 0 : A[minr][maxc], d = minr == -1 || minc == -1 ? 0 : A[minr][minc]; ans[i][j] = a - b - c + d; } } return ans; } }; -
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 -
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 } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }