Matrix Block Sum

Matrix Block Sum

What is this problem about?

The Matrix Block Sum problem provides an m x n matrix and an integer k. You need to return a new matrix of the same size where every element answer[i][j] is the sum of all elements matrix[r][c] such that r is between i - k and i + k, and c is between j - k and j + k (essentially, a square block centered around (i, j)).

Why is this asked in interviews?

This is the textbook problem for teaching 2D Prefix Sums. A naive solution involves 4 nested loops (iterating over every cell, then iterating over its $K \times K$ block) leading to $O(M \times N \times K^2)$ time. Interviewers ask this to verify if you can apply dynamic programming concepts to geometry, flattening the time complexity down to a strict $O(M \times N)$ regardless of how large k is.

Algorithmic pattern used

This utilizes the 2D Prefix Sum pattern.

1. Build a prefix sum matrix where prefix[r][c] stores the sum of all elements in the rectangle from (0,0) to (r, c). prefix[r][c] = mat[r][c] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1]
2. For any block defined by (r1, c1) as top-left and (r2, c2) as bottom-right, the sum is calculated in $O(1)$ time: sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1] You just need to handle the boundary conditions so r1, c1, r2, and c2 don't go out of the matrix bounds.

Example explanation

Let k = 1. For cell (1, 1), we want the sum of the block from (0, 0) to (2, 2). Instead of looping 9 times to add the cells, we use the precomputed prefix matrix. sum = prefix[2][2] - prefix[-1][2] - prefix[2][-1] + prefix[-1][-1] Handling bounds, anything $< 0$ is just 0. So sum = prefix[2][2] - 0 - 0 + 0 = prefix[2][2]. For cell (2, 2), the block is (1, 1) to (3, 3). Assuming (3,3) is out of bounds, we cap it at the max row/col. The calculation becomes a simple $O(1)$ lookup for every single cell.

Common mistakes candidates make

A very common mistake is dealing with the matrix boundaries clumsily. Candidates often write dozens of if statements to handle edges. A cleaner way is to simply allocate the prefix sum matrix with size (m+1) x (n+1) and 1-index it. This provides a buffer of zeroes at row 0 and col 0, automatically resolving the -1 index out-of-bounds issues without complex branching logic.

Interview preparation tip

Memorize the 2D Prefix Sum formulas. They are standard tools that every senior engineer should know. Building: P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]. Querying: Sum(r1,c1 to r2,c2) = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]. Writing this fluently shows immense mathematical and algorithmic maturity.