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
Solution: 2D range query
Time complexity: O(m*n)
Space complexity: O(m*n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua, 20 ms class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) { const int n = mat.size(); const int m = mat[0].size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1)); for (int y = 1; y <= n; ++y) for (int x = 1; x <= m; ++x) dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + mat[y - 1][x - 1] - dp[y - 1][x - 1]; auto ans = mat; for (int y = 1; y <= n; ++y) for (int x = 1; x <= m; ++x) { int x1 = max(1, x - K); int x2 = min(m, x + K); int y1 = max(1, y - K); int y2 = min(n, y + K); ans[y - 1][x - 1] = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1]; } return ans; } }; |