Matrix Block Sum

The problem is asking us to compute the sum of the elements in a block of size (2k + 1) around each cell of a given matrix mat. Here’s a step-by-step Python solution to achieve this:

  1. Create a Prefix Sum Matrix: First, we’ll create a prefix sum matrix prefix_sum of the same size as mat. The value at prefix_sum[i][j] will be the sum of all elements in mat that are in the top-left rectangle formed by (0,0) to (i,j).
  2. Use Prefix Sum to Compute Block Sum: Next, we’ll compute the block sum for each position (i,j) using the prefix sum matrix. We’ll define four corner points of the block and use them to get the sum using the prefix sum matrix.
  3. Return the Result: The computed block sum for each (i,j) will be the result, and we’ll return it.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]

        # Compute the prefix sum matrix
        for i in range(m):
            for j in range(n):
                prefix_sum[i + 1][j + 1] = mat[i][j] + prefix_sum[i + 1][j] + prefix_sum[i][j + 1] - prefix_sum[i][j]

        # Function to get the prefix sum for a given rectangle
        def get_sum(x1, y1, x2, y2):
            return prefix_sum[x2 + 1][y2 + 1] - prefix_sum[x2 + 1][y1] - prefix_sum[x1][y2 + 1] + prefix_sum[x1][y1]

        # Compute the block sum using the prefix sum
        result = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r1, c1, r2, c2 = max(i - k, 0), max(j - k, 0), min(i + k, m - 1), min(j + k, n - 1)
                result[i][j] = get_sum(r1, c1, r2, c2)

        return result

This solution will compute the required block sum for the entire matrix, adhering to the constraints and conditions mentioned in the problem statement.