LeetCode 1314. Matrix Block Sum

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.length`
• `n == mat[i].length`
• `1 <= m, n, k <= 100`
• `1 <= 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).