DSA problem
Matrix Block Sum
Given an m x n matrix mat and an integer k, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for:
i - k <= r <= i + k,j - k <= c <= j + k, and(r, c)is a valid position in the matrix.
In other words, every output cell is the sum of a square block of side 2k + 1 centered on that cell, clipped to the matrix boundaries. Computing each block independently would be expensive, so we build a 2D prefix-sum table once and answer each block in O(1) time by clamping the block corners to valid indices and applying inclusion-exclusion.
Examples
Example 1
Input:
mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1Output:
[[12,21,16],[27,45,33],[24,39,28]]Explanation: For answer[0][0], the block covers rows 0..1 and cols 0..1: 1+2+4+5 = 12. For answer[1][1], the block covers the whole matrix: 1+2+...+9 = 45.
Example 2
Input:
mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2Output:
[[45,45,45],[45,45,45],[45,45,45]]Explanation: With k = 2 every block spans the entire 3x3 matrix, so every cell equals the total sum 45.
Constraints
- m == mat.length
- n == mat[i].length
- 1 <= m, n, k <= 100
- 1 <= mat[i][j] <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.