Matrix Block Sum
Medium · Matrix · Array · Matrix · Prefix Sum
Problem
You are given an m x n grid of numbers mat and an integer k. Build a grid answer of the same size where answer[i][j] is the sum of every mat[r][c] within k steps of (i, j) in both directions:
i - k <= r <= i + k and j - k <= c <= j + k, counting only cells that lie inside the grid.
In other words, center a (2k + 1) x (2k + 1) square on each cell, cut off whatever falls outside the grid, and add up what is left. This is the “box blur” used in image processing, without the final division.
Examples
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[12,21,16],[27,45,33],[24,39,28]]
The center cell’s block is the whole grid: 45. The top-left cell’s block is the 2 x 2 corner 1 + 2 + 4 + 5 = 12, because the rest of its square falls outside.
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2 Output: [[45,45,45],[45,45,45],[45,45,45]]
With k = 2 every cell’s block covers the whole 3 x 3 grid.
Input: mat = [[1,0,2,0,3]], k = 1 Output: [[1,3,2,5,3]]
A single row: each answer is the cell plus its left and right neighbors, where they exist.
Constraints
- 1 <= m, n <= 100
- 1 <= k <= 100
- 1 <= mat[i][j] <= 100
Approaches
- Baseline: add up every block directly — time O(m · n · k²), space O(1) besides the output
Follow-up
What if cells of mat change between queries? A static prefix table must be rebuilt after every change. A 2-D Fenwick tree (binary indexed tree) supports both a cell update and a rectangle sum in O(log m · log n).
Related problems
Start free on Cariara · Coding problems · System design studio
