Matrix Block Sum

Try it yourself

MediumProblemExternal linkUpdated Oct 25, 2026

Description

You get an m x n matrix mat and an integer k.

Return an m x n matrix answer where answer[i][j] is the sum of every mat[r][c] with

i - k ≤ r ≤ i + k,
j - k ≤ c ≤ j + k, and
(r, c) inside the matrix.

In other words, each cell gets the sum of the block reaching k cells out in every direction, cut off at the edges.

Examples

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]]

Explanation: The block around the middle cell is the whole matrix, 45. The block around the top-left cell is cut off at the edges: 1 + 2 + 4 + 5 = 12.

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]]

Explanation: With k = 2 every block covers the whole matrix, so every cell gets 45.

Example 3

Input: mat = [[5]], k = 3

Output: [[5]]

Explanation: One cell: its block is just itself.

Constraints

m == mat.length, n == mat[i].length
1 ≤ m, n, k ≤ 100
1 ≤ mat[i][j] ≤ 100

Editorial

Brute Force

Intuition

For every cell, work out where its block starts and ends (clamped to the matrix), and add up every cell in it.

Step-by-Step Explanation

For mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and k = 1:

For each cell, add up every cell within 1 row and column of it, stopping at the edges.
Cell (0, 0) covers rows 0..1 and columns 0..1, 4 cells that add up to 12.
Cell (0, 1) covers rows 0..1 and columns 0..2, 6 cells that add up to 21.
Cell (0, 2) covers rows 0..1 and columns 1..2, 4 cells that add up to 16.
Cell (1, 0) covers rows 0..2 and columns 0..1, 6 cells that add up to 27.
Cell (1, 1) covers rows 0..2 and columns 0..2, 9 cells that add up to 45.
Cell (1, 2) covers rows 0..2 and columns 1..2, 6 cells that add up to 33.
Cell (2, 0) covers rows 1..2 and columns 0..1, 4 cells that add up to 24.
Cell (2, 1) covers rows 1..2 and columns 0..2, 6 cells that add up to 39.
Cell (2, 2) covers rows 1..2 and columns 1..2, 4 cells that add up to 28.
Every block was added from scratch, 49 additions in all, though neighbouring blocks share most of their cells.

Add Up Each Block — Blue: the cell. Amber: the rest of its block.

Algorithm

For each cell (i, j): rows max(0, i − k) to min(m − 1, i + k), columns max(0, j − k) to min(n − 1, j + k).
Add up every cell in that block.

Code

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> answer(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)         // add up this cell's block, cut off at the edges
                for (int r = max(0, i - k); r <= min(m - 1, i + k); r++)
                    for (int c = max(0, j - k); c <= min(n - 1, j + k); c++)
                        answer[i][j] += mat[r][c];
        return answer;
    }
};

class Solution:
    def matrixBlockSum(self, mat: list[list[int]], k: int) -> list[list[int]]:
        m, n = len(mat), len(mat[0])
        answer = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):                  # add up this cell's block, cut off at the edges
                total = 0
                for r in range(max(0, i - k), min(m, i + k + 1)):
                    for c in range(max(0, j - k), min(n, j + k + 1)):
                        total += mat[r][c]
                answer[i][j] = total
        return answer

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] answer = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)         // add up this cell's block, cut off at the edges
                for (int r = Math.max(0, i - k); r <= Math.min(m - 1, i + k); r++)
                    for (int c = Math.max(0, j - k); c <= Math.min(n - 1, j + k); c++)
                        answer[i][j] += mat[r][c];
        return answer;
    }
}

var matrixBlockSum = function(mat, k) {
    const m = mat.length, n = mat[0].length;
    const answer = Array.from({ length: m }, () => new Array(n).fill(0));
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)             // add up this cell's block, cut off at the edges
            for (let r = Math.max(0, i - k); r <= Math.min(m - 1, i + k); r++)
                for (let c = Math.max(0, j - k); c <= Math.min(n - 1, j + k); c++)
                    answer[i][j] += mat[r][c];
    return answer;
};

Complexity Analysis

Time Complexity: O(m · n · k²)

Each block can hold up to (2k + 1)² cells, capped by the matrix.

Space Complexity: O(1) beyond the answer.

Why This Approach Is Not Efficient

On a 100 × 100 matrix with k = 100, every block is the whole matrix: 10^4 cells times 10^4 additions is 10^8 (over the time limit in Python).

Neighbouring blocks share almost all their cells, and each block is just a rectangle. A table of 2D running totals answers any rectangle's sum in O(1).

Optimal Approach - 2D Prefix Sums

Intuition

Build P once: P[r][c] is the sum of the rectangle above and left of (r, c), with a row and a column of zeros in front. Each new entry is its cell, plus the block above, plus the block on the left, minus the block above-left, which those two both contain.

Then each cell's block is a rectangle from (r1, c1) to (r2, c2), clamped to the matrix on both sides, and its sum is four lookups:

P[r2 + 1][c2 + 1] − P[r1][c2 + 1] − P[r2 + 1][c1] + P[r1][c1]

Everything down to the corner, minus the rows above, minus the columns to the left, plus the top-left block that was taken away twice.

Step-by-Step Explanation

For mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and k = 1:

The table P is built once. P[r][c] is the sum of everything above and left of (r, c), with a row and a column of zeros in front. Each cell's block is now four lookups.
Cell (0, 0) covers rows 0..1 and columns 0..1, so its sum is P[2][2] − P[0][2] − P[2][0] + P[0][0] = 12 − 0 − 0 + 0 = 12.
Cell (0, 1) covers rows 0..1 and columns 0..2, so its sum is P[2][3] − P[0][3] − P[2][0] + P[0][0] = 21 − 0 − 0 + 0 = 21.
Cell (0, 2) covers rows 0..1 and columns 1..2, so its sum is P[2][3] − P[0][3] − P[2][1] + P[0][1] = 21 − 0 − 5 + 0 = 16.
Cell (1, 0) covers rows 0..2 and columns 0..1, so its sum is P[3][2] − P[0][2] − P[3][0] + P[0][0] = 27 − 0 − 0 + 0 = 27.
Cell (1, 1) covers rows 0..2 and columns 0..2, so its sum is P[3][3] − P[0][3] − P[3][0] + P[0][0] = 45 − 0 − 0 + 0 = 45.
Cell (1, 2) covers rows 0..2 and columns 1..2, so its sum is P[3][3] − P[0][3] − P[3][1] + P[0][1] = 45 − 0 − 12 + 0 = 33.
Cell (2, 0) covers rows 1..2 and columns 0..1, so its sum is P[3][2] − P[1][2] − P[3][0] + P[1][0] = 27 − 3 − 0 + 0 = 24.
Cell (2, 1) covers rows 1..2 and columns 0..2, so its sum is P[3][3] − P[1][3] − P[3][0] + P[1][0] = 45 − 6 − 0 + 0 = 39.
Cell (2, 2) covers rows 1..2 and columns 1..2, so its sum is P[3][3] − P[1][3] − P[3][1] + P[1][1] = 45 − 6 − 12 + 1 = 28.
The answer, from 36 lookups, whatever k is.

Four Lookups per Cell — The table P. Green: the total down to the block's corner. Amber: the two strips taken off. Violet: the corner added back.

Algorithm

Build P with m + 1 rows and n + 1 columns: P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c] − P[r][c].
For each cell (i, j): clamp 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].

Code

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> P(m + 1, vector<int>(n + 1, 0));   // P[r][c] = sum of rows 0..r-1, columns 0..c-1
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)         // the block above and the block on the left both hold P[r][c]
                P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
        vector<vector<int>> answer(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int r1 = max(0, i - k), c1 = max(0, j - k);                   // clamp the block to the matrix
                int 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;
    }
};

class Solution:
    def matrixBlockSum(self, mat: list[list[int]], k: int) -> list[list[int]]:
        m, n = len(mat), len(mat[0])
        P = [[0] * (n + 1) for _ in range(m + 1)]   # P[r][c] = sum of rows 0..r-1 and columns 0..c-1
        for r in range(m):
            for c in range(n):                  # the block above and the block on the left both hold P[r][c]
                P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]
        answer = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                r1, c1 = max(0, i - k), max(0, j - k)       # clamp the block to the matrix, on both sides
                r2, c2 = min(m - 1, i + k), 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

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] P = new int[m + 1][n + 1];      // P[r][c] = sum of rows 0..r-1 and columns 0..c-1
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)         // the block above and the block on the left both hold P[r][c]
                P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
        int[][] answer = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int r1 = Math.max(0, i - k), c1 = Math.max(0, j - k);         // clamp the block to the matrix
                int r2 = Math.min(m - 1, i + k), c2 = Math.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;
    }
}

var matrixBlockSum = function(mat, k) {
    const m = mat.length, n = mat[0].length;
    const P = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));   // rows 0..r-1, columns 0..c-1
    for (let r = 0; r < m; r++)
        for (let c = 0; c < n; c++)             // the block above and the block on the left both hold P[r][c]
            P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
    const answer = [];
    for (let i = 0; i < m; i++) {
        const row = [];
        for (let j = 0; j < n; j++) {
            const r1 = Math.max(0, i - k), c1 = Math.max(0, j - k);           // clamp the block to the matrix
            const r2 = Math.min(m - 1, i + k), c2 = Math.min(n - 1, j + k);
            row.push(P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]);
        }
        answer.push(row);
    }
    return answer;
};

Complexity Analysis

Time Complexity: O(m · n)

One pass to build the table, four lookups per cell, whatever k is.

Space Complexity: O(m · n) for the table.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Clamping only the bottom-right side. r1, c1 = i - k, j - k

On mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 1, it returns [[9,-24,-17],[-18,45,33],[-15,39,28]]; the answer is [[12,21,16],[27,45,33],[24,39,28]]. Near the top or left edge, i - k is negative. Python doesn't complain: P[-1] is the table's last row, so the block quietly gets the wrong sum. Clamp both sides, max(0, i - k) as well as min(m - 1, i + k).

Building the table without taking off the overlap. P[r + 1][c + 1] = mat[r][c] + P[r][c + 1] + P[r + 1][c]

On mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 1, it returns [[13,25,20],[33,67,55],[30,61,50]]; the answer is [[12,21,16],[27,45,33],[24,39,28]]. P[r][c + 1] (the block above) and P[r + 1][c] (the block on the left) both contain the block above-left, so adding both counts it twice. Take P[r][c] off once.

Clamping to m instead of m − 1. r2, c2 = min(m, i + k), min(n, j + k)

On mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 1, it crashes with IndexError: list index out of range; the answer is [[12,21,16],[27,45,33],[24,39,28]]. The last row is m - 1. Clamping to m makes P[r2 + 1] read row m + 1 of a table that only goes up to row m, which crashes.

Where This Pattern Is Taught

This problem practises 2D prefix sums: any rectangle from four totals. It's taught in Difference Arrays and 2D Prefix Sums.