Description
https://leetcode.com/problems/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.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100
Explanation
Implement as the problem describes.
Python Solution
class Solution:
def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
results = []
for i in range(len(mat)):
results.append([])
for j in range(len(mat[0])):
results[i].append([None])
for i in range(len(mat)):
for j in range(len(mat[0])):
value_sum = 0
for m in range(max(i - k, 0), min(i + k + 1, len(mat))):
for n in range(max(j - k, 0), min(j + k + 1, len(mat[0]))):
value_sum += mat[m][n]
results[i][j] = value_sum
return results- Time Complexity: O(N^4).
- Space Complexity: O(N^2).