1314. Matrix Block Sum | LEETCODE MEDIUM | DYNAMIC PROGRAMMING | CODE EXPLAINER
Matrix Block Sum - Video Solution
Watch 10 video solutions for Matrix Block Sum, a medium level problem involving Array, Matrix, Prefix Sum. This walkthrough by code Explainer has 10,293 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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] <= 100
Approach Overview
Problem 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.
Complexity Analysis
| 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 |