Matrix Block Sum

You are given an m x n matrix mat and an integer k. For every cell (i, j), you need to compute the sum of all elements inside the block from (i - k, j - k) to (i + k, j + k), clamping the boundaries so you never go outside the matrix. Return the resulting answer matrix.

This is LeetCode 1314: Matrix Block Sum, a medium problem that combines 2D prefix sums with careful index clamping. Once you see that each block sum is just a rectangular region query, the entire problem reduces to something you may have already solved in Range Sum Query 2D.

Why this problem matters

At the surface, this looks like nested loops: for every cell, iterate over a (2k+1) x (2k+1) window and add up values. That brute force approach runs in O(m * n * k^2), which gets expensive quickly. With m, n up to 100 and k up to 100, the worst case is millions of operations per cell.

The real test is whether you recognize the pattern. Every block sum is the sum of a rectangular subregion of the matrix. You have already seen how to answer rectangular sum queries in O(1) using a 2D prefix sum. This problem is asking you to perform that query m * n times, once per cell.

This pattern shows up frequently in image processing (box blur filters), game development (area damage calculations), and data analysis (moving window aggregations over grids). Learning it once pays dividends across many domains.

The key insight

Each answer[i][j] is the sum of mat values inside a rectangle. The rectangle's corners are (max(0, i-k), max(0, j-k)) for the top-left and (min(m-1, i+k), min(n-1, j+k)) for the bottom-right. If you precompute a 2D prefix sum matrix, you can answer each of these rectangle queries in O(1).

The total work becomes O(m * n) for building the prefix sum, plus O(m * n) for filling in the answer matrix, giving O(m * n) overall. That is independent of k.

The solution

def matrixBlockSum(mat, k):
    m, n = len(mat), len(mat[0])
    P = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            P[i][j] = (
                mat[i - 1][j - 1]
                + P[i - 1][j]
                + P[i][j - 1]
                - P[i - 1][j - 1]
            )

    answer = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            r1 = max(0, i - k)
            c1 = max(0, j - k)
            r2 = min(m - 1, i + k)
            c2 = min(n - 1, j + k)
            answer[i][j] = (
                P[r2 + 1][c2 + 1]
                - P[r1][c2 + 1]
                - P[r2 + 1][c1]
                + P[r1][c1]
            )

    return answer

The solution has two phases. First, build a 2D prefix sum matrix P with an extra row and column of zeros for boundary handling. Second, for each cell (i, j), clamp the block boundaries to stay within the matrix, then use the inclusion-exclusion formula to look up the block sum in O(1).

The inclusion-exclusion formula works like this: start with the sum of the full rectangle from (0,0) to (r2, c2). Subtract the strip above the block. Subtract the strip to the left of the block. Add back the top-left corner that was subtracted twice.

Visual walkthrough

Notice how the block size varies at the edges. For corner cell (0,0), the block is only 2x2 because clamping cuts off the negative indices. For center cell (1,1), the block covers the full 3x3 matrix. The prefix sum formula handles both cases identically, with no branching needed.

Complexity analysis

The brute force iterates over a (2k+1) x (2k+1) window for each of the m * n cells. The prefix sum approach does O(m * n) precomputation and then O(1) per cell, removing all dependence on k. The space is the same either way since you need to store the answer matrix.

The building blocks

1. 2D prefix sum construction

def build_2d_prefix(matrix):
    m, n = len(matrix), len(matrix[0])
    P = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            P[i][j] = (
                matrix[i - 1][j - 1]
                + P[i - 1][j]
                + P[i][j - 1]
                - P[i - 1][j - 1]
            )
    return P

This is the same recurrence used in Range Sum Query 2D. Each entry P[i][j] stores the sum of all elements from (0,0) to (i-1, j-1) in the original matrix. The zero padding along row 0 and column 0 means you never need to check for out-of-bounds access during construction.

2. Clamped rectangular region query

def block_sum(P, i, j, k, m, n):
    r1 = max(0, i - k)
    c1 = max(0, j - k)
    r2 = min(m - 1, i + k)
    c2 = min(n - 1, j + k)
    return (
        P[r2 + 1][c2 + 1]
        - P[r1][c2 + 1]
        - P[r2 + 1][c1]
        + P[r1][c1]
    )

The max and min calls clamp the block so it fits within the matrix. After clamping, the inclusion-exclusion formula is identical to a standard 2D prefix sum query. This pattern of clamping then querying appears in any problem that uses a sliding window over a 2D grid.

Edge cases

• k = 0: every block is just the single cell itself. The answer matrix equals the input matrix.
• k larger than the matrix: every block covers the entire matrix. Every cell in the answer has the same value, the total sum of all elements.
• Single row or single column: the 2D prefix sum degenerates to a 1D prefix sum, but the formula still works without any special handling.
• 1x1 matrix: the answer is always the single element, regardless of k.
• Negative values in the matrix: prefix sums and inclusion-exclusion work correctly with negative numbers. No special treatment needed.

From understanding to recall

You now see how 2D prefix sums turn an expensive per-cell computation into a constant-time lookup. The inclusion-exclusion formula, the zero-padded prefix matrix, and the boundary clamping all fit together cleanly. But in an interview, the index arithmetic is where mistakes happen. Is it r2 + 1 or r2? Do you clamp before or after adding 1?

Spaced repetition closes that gap. You write the prefix sum construction and the clamped query formula from scratch, verify the output on a small example, and repeat at increasing intervals. After a few rounds, the offsets become automatic. You stop second-guessing and start writing.

Related posts

• Prefix Sum Pattern - 2D prefix sums
• 01 Matrix - Another matrix BFS/DP problem
• Maximal Square - DP on a 2D grid

Matrix Block Sum is a clean application of 2D prefix sums. Once you internalize the inclusion-exclusion formula and the boundary clamping pattern, you can solve it and dozens of similar problems without hesitation.