Matrix Block Sum

Medium
905.

Matrix Block Sum

Matrix Block Sum is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google and Adobe interviews.

Return a matrix answer of the same size as mat where answer[i][j] is the sum of all mat[r][c] with i - k <= r <= i + k and j - k <= c <= j + k, counting only positions inside the matrix.

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

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
A radius of 2 covers the whole matrix from every cell.

Example 3

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

Constraints

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= mat[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[][]}
 */
var matrixBlockSum = function(mat, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Matrix Block Sum — Solution in Python, Java & C++

Matrix Block Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.

Matrix Block Sum is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Prefix Sum
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return a matrix answer of the same size as mat where answer[i][j] is the sum of all mat[r][c] with i - k <= r <= i + k and j - k <= c <= j + k, counting only positions inside the matrix.

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

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: A radius of 2 covers the whole matrix from every cell.

Example 3

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

Constraints

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

Hints for Matrix Block Sum

  1. Hint 1

    Summing each block directly is O(m · n · k²).

  2. Hint 2

    Build a 2D prefix-sum table so any rectangle's sum is four lookups.

  3. Hint 3

    Clamp the block's corners to the matrix before querying.

How to solve Matrix Block Sum

Precompute a 2D prefix-sum table, then answer every block with the standard inclusion-exclusion of four corners. Clamping handles blocks that hang over the edges.

Approach

  1. Build pre with an extra zero row and column, where pre[i+1][j+1] is the sum of mat[0…i][0…j].
  2. For each cell, clamp the block to [max(0, i-k), min(m-1, i+k)] and likewise for columns.
  3. The block sum is pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1].

Why it works

The four-corner formula subtracts the two overlapping strips and adds back the doubly-subtracted corner — plain inclusion-exclusion. The padding row and column remove every boundary special case, which is what makes the clamped indices safe to use directly.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Forgetting the + pre[r1][c1] term double-subtracts the overlap.
  • The clamp is on the block, not on the prefix indices — the padded table then handles the rest.
  • The totals reach 100 · 100 · 100 = 10^6, comfortably inside int.

Reference solution

Python

from typing import List

def matrixBlockSum(mat: List[List[int]], k: int) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    pre = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            pre[i + 1][j + 1] = mat[i][j] + pre[i][j + 1] + pre[i + 1][j] - pre[i][j]
    out = []
    for i in range(m):
        row = []
        for j in range(n):
            r1, c1 = max(0, i - k), max(0, j - k)
            r2, c2 = min(m - 1, i + k), min(n - 1, j + k)
            row.append(pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1])
        out.append(row)
    return out

Java

public static int[][] matrixBlockSum(int[][] mat, int k) {
    int m = mat.length, n = mat[0].length;
    int[][] pre = new int[m + 1][n + 1];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            pre[i + 1][j + 1] = mat[i][j] + pre[i][j + 1] + pre[i + 1][j] - pre[i][j];
        }
    }
    int[][] out = 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);
            int r2 = Math.min(m - 1, i + k), c2 = Math.min(n - 1, j + k);
            out[i][j] = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
        }
    }
    return out;
}

C++

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
    int m = (int) mat.size(), n = (int) mat[0].size();
    vector<vector<int>> pre(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            pre[i + 1][j + 1] = mat[i][j] + pre[i][j + 1] + pre[i + 1][j] - pre[i][j];
        }
    }
    vector<vector<int>> out(m, vector<int>(n, 0));
    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);
            int r2 = min(m - 1, i + k), c2 = min(n - 1, j + k);
            out[i][j] = pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
        }
    }
    return out;
}

JavaScript

var matrixBlockSum = function(mat, k) {
    var m = mat.length, n = mat[0].length, i, j;
    var pre = [];
    for (i = 0; i <= m; i++) {
        var prow = [];
        for (j = 0; j <= n; j++) prow.push(0);
        pre.push(prow);
    }
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            pre[i + 1][j + 1] = mat[i][j] + pre[i][j + 1] + pre[i + 1][j] - pre[i][j];
        }
    }
    var out = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) {
            var r1 = Math.max(0, i - k), c1 = Math.max(0, j - k);
            var r2 = Math.min(m - 1, i + k), c2 = Math.min(n - 1, j + k);
            row.push(pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1]);
        }
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal