Given a m x n matrix mat and an integer k, return a matrixanswerwhere eachanswer[i][j]is the sum of all elementsmat[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
Solutions
Solution 1: Two-Dimensional Prefix Sum
This problem is a template for two-dimensional prefix sum.
We define $s[i][j]$ as the sum of the elements in the first $i$ rows and the first $j$ columns of the matrix $mat$. The calculation formula for $s[i][j]$ is:
In this way, we can quickly calculate the sum of elements in any rectangular area through the $s$ array.
For a rectangular area with the upper left coordinate $(x_1, y_1)$ and the lower right coordinate $(x_2, y_2)$, we can calculate the sum of its elements through the $s$ array:
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the number of rows and columns in the matrix, respectively.