Matrix Block Sum LeetCode solution in Python

1
# Runtime: 308 ms (Top 20.31%) | Memory: 15.2 MB (Top 51.05%)
2
class Solution:
3
    def matrixBlockSum(self, matrix: List[List[int]], k: int) -> List[List[int]]:
4
        ROWS, COLS = len(matrix), len(matrix[0])
5

6
        prefix_sums = [[0] * (COLS + 1) for _ in range(ROWS + 1)]
7

8
        for r in range(1, ROWS + 1):
9
            for c in range(1, COLS + 1):
10
                prefix_sums[r][c] = (
11
                    prefix_sums[r - 1][c]
12
                    + prefix_sums[r][c - 1]
13
                    + matrix[r - 1][c - 1]
14
                    - prefix_sums[r - 1][c - 1]
15
                )
16

17
        res = [[0] * COLS for _ in range(ROWS)]
18
        for r in range(ROWS):
19
            for c in range(COLS):
20
                res[r][c] = (
21
                    prefix_sums[min(r + k + 1, ROWS)][min(c + k + 1, COLS)]
22
                    - prefix_sums[max(r - k, 0)][min(c + k + 1, COLS)]
23
                    - prefix_sums[min(r + k + 1, ROWS)][max(c - k, 0)]
24
                    + prefix_sums[max(r - k, 0)][max(c - k, 0)]
25
                )
26

27
        return res