Given a 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.
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]]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100Problem Overview: Given an m x n matrix mat and an integer k, compute a new matrix where each cell contains the sum of all elements within a square block centered at that cell with radius k. The block includes all positions (r, c) such that |r - i| ≤ k and |c - j| ≤ k, clipped to the matrix boundaries.
Approach 1: Brute Force Block Traversal (O(m * n * k²) time, O(1) space)
For every cell (i, j), iterate through the entire block defined by rows [i - k, i + k] and columns [j - k, j + k]. Clamp the boundaries so they stay within the matrix. Accumulate the sum of each valid element and store it in the result matrix. This approach directly simulates the definition of the block sum using nested loops. The implementation is straightforward but inefficient when k is large because each cell recomputes overlapping regions repeatedly. Time complexity becomes O(m * n * (2k+1)²), which simplifies to O(m * n * k²), while extra space remains O(1) aside from the output.
Approach 2: 2D Prefix Sum (O(m * n) time, O(m * n) space)
Use a 2D prefix matrix where each entry stores the sum of the submatrix from (0,0) to (i,j). This preprocessing step takes O(m * n) time. Once built, you can compute the sum of any rectangular region in constant time using inclusion–exclusion: sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]. For each cell, determine the block boundaries r1 = max(0, i-k), c1 = max(0, j-k), r2 = min(m-1, i+k), and c2 = min(n-1, j+k). Query the prefix matrix to compute the block sum instantly. This removes repeated summation of overlapping regions and reduces the overall complexity to O(m * n) time with O(m * n) auxiliary space.
The prefix sum idea is a common pattern when solving range-sum problems on a matrix. Instead of recomputing sums repeatedly, you preprocess cumulative values once and reuse them for constant-time queries. The same technique appears in many array range problems and sliding window variants.
Recommended for interviews: The 2D prefix sum approach is the expected solution. Interviewers want to see whether you recognize repeated submatrix queries and convert them into constant-time lookups using a prefix sum structure. Implementing the brute force solution first shows you understand the problem constraints, but moving to prefix sums demonstrates algorithmic optimization and familiarity with common matrix techniques.
This approach involves directly computing the sum of elements in the k-neighborhood for each element in the matrix. We iterate over each element and within it, we iterate over its neighbors bounded by k, ensuring to remain within matrix boundaries.
This C code uses a brute force approach to calculate the matrix block sum for a given input matrix and k. It iterates over each matrix element and sums up all values around it within the given range k, making sure to stay within the matrix boundaries. For each matrix element mat[i][j], the sum of values within (i-k) to (i+k) and (j-k) to (j+k) is calculated.
Time Complexity: O(m * n * k * k) where m and n are the dimensions of the matrix and k is the range.
Space Complexity: O(1) as we're utilizing an extra matrix of the same size.
To solve the problem efficiently, we can use a prefix sum array. This involves building a cumulative sum matrix such that each entry at (i,j) contains the sum of elements from (0,0) to (i,j). Using this, we can compute any submatrix sum in constant time.
This C solution uses a prefix sum matrix to calculate the sum of any submatrix. The cumulative sum is calculated using an auxiliary matrix which enables retrieving any submatrix sum in constant time, thus reducing overall computational complexity.
Time Complexity: O(m * n) for prefix sum computation and submatrix retrieval.
Space Complexity: O(m * n) for auxiliary storage.
This problem is a template for two-dimensional prefix sum.
We define s[i][j] as the sum of the elements in the first i rows and the first j columns of the matrix mat. The calculation formula for s[i][j] is:
$
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]
In this way, we can quickly calculate the sum of elements in any rectangular area through the s array.
For a rectangular area with the upper left coordinate (x_1, y_1) and the lower right coordinate (x_2, y_2), we can calculate the sum of its elements through the s array:
s[x_2+1][y_2+1] - s[x_1][y_2+1] - s[x_2+1][y_1] + s[x_1][y_1]
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n$ are the number of rows and columns in the matrix, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(m * n * k * k) where m and n are the dimensions of the matrix and k is the range. |
| Optimized Prefix Sum Approach | Time Complexity: O(m * n) for prefix sum computation and submatrix retrieval. |
| Two-Dimensional Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Block Traversal | O(m * n * k²) | O(1) | Small matrices or small k where performance is not critical |
| 2D Prefix Sum | O(m * n) | O(m * n) | General case and interview settings with frequent submatrix sum queries |
1314. Matrix Block Sum | LEETCODE MEDIUM | DYNAMIC PROGRAMMING | CODE EXPLAINER • code Explainer • 9,964 views views
Watch 9 more video solutions →Practice Matrix Block Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor