Matrix Block Sum solution and explanation
Google
9 more videos on this problem
1314. Matrix Block Sum | LEETCODE MEDIUM | DYNAMIC PROGRAMMING | CODE EXPLAINERcode Explainer · 11:52 · 10K views
LeetCode 1314. Matrix Block SumHappy Coding · 17:42 · 8K views
Matrix Block Sum – 2D Prefix Sum | Running Sum of 2D Array | C++, Java, PythonRisingBrain · 33:56 · 6K views
Leetcode 1314: Matrix Block SumAlgorithms Casts · 35:33 · 6K views
2D Prefix Sum Interview Pattern | 1314 Matrix Block SumBharat Khanna · 14:25 · 3K views
CP1 Topic 3: Video 4: Matrix Block SumCoach355 · 14:23 · 3K views
8. Matrix Block Sum | 2-D Prefix Sum | Dynamic Programming | LeetCode Medium 1314AceCoder Academy · 44:34 · 2K views
LeetCode 1314 | Matrix Block Sum | Matrix | JavaSleepy Cracker · 11:55 · 1K views
Live Coding Leetcode 1314: Matrix Block SumCS Live Coding · 30:23 · 862 views
Matrix Block Sum | Leetcode 1314 | HindiCore Concepts · 9:02 · 292 views
The problem
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.
Approach 1: Brute Force Approach
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.
def matrixBlockSum(mat, k):
m, n = len(mat), len(mat[0])
answer = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
total = 0
for r in range(max(0, i - k), min(m, i + k + 1)):
for c in range(max(0, j - k), min(n, j + k + 1)):
total += mat[r][c]
answer[i][j] = total
return answerclass Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
int[][] answer = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int sum = 0;
for (int r = Math.max(0, i - k); r <= Math.min(m - 1, i + k); r++) {
for (int c = Math.max(0, j - k); c <= Math.min(n - 1, j + k); c++) {
sum += mat[r][c];
}
}
answer[i][j] = sum;
}
}
return answer;
}
}#include <vector>
using namespace std;
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> answer(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int sum = 0;
for (int r = max(0, i - k); r <= min(m - 1, i + k); ++r) {
for (int c = max(0, j - k); c <= min(n - 1, j + k); ++c) {
sum += mat[r][c];
}
}
answer[i][j] = sum;
}
}
return answer;
}var matrixBlockSum = function(mat, k) {
const m = mat.length, n = mat[0].length;
const answer = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let sum = 0;
for (let r = Math.max(0, i - k); r <= Math.min(m - 1, i + k); r++) {
for (let c = Math.max(0, j - k); c <= Math.min(n - 1, j + k); c++) {
sum += mat[r][c];
}
}
answer[i][j] = sum;
}
}
return answer;
};#include <stdio.h>
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
void matrixBlockSum(int** mat, int matSize, int* matColSize, int k, int** returnMat) {
int m = matSize, n = matColSize[0];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int sum = 0;
for (int r = MAX(0, i - k); r <= MIN(m - 1, i + k); ++r) {
for (int c = MAX(0, j - k); c <= MIN(n - 1, j + k); ++c) {
sum += mat[r][c];
}
}
returnMat[i][j] = sum;
}
}
}public class Solution {
public int[][] MatrixBlockSum(int[][] mat, int k) {
int m = mat.Length, n = mat[0].Length;
int[][] answer = new int[m][];
for (int i = 0; i < m; ++i) {
answer[i] = new int[n];
for (int j = 0; j < n; ++j) {
int sum = 0;
for (int r = Math.Max(0, i - k); r <= Math.Min(m - 1, i + k); ++r) {
for (int c = Math.Max(0, j - k); c <= Math.Min(n - 1, j + k); ++c) {
sum += mat[r][c];
}
}
answer[i][j] = sum;
}
}
return answer;
}
}This Python solution iterates through the matrix, calculating the sum using two inner loops that determine the valid range bounded by k for each matrix entry.
Time Complexity: O(m * n * k * k).
Space Complexity: O(m * n) due to the result matrix.
Approach 2: Optimized Prefix Sum Approach
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.
def matrixBlockSum(mat, k):
m, n = len(mat), len(mat[0])
summ = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
summ[i][j] = mat[i - 1][j - 1] + summ[i - 1][j] + summ[i][j - 1] - summ[i - 1][j - 1]
answer = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
r1, c1 = max(0, i - k), max(0, j - k)
r2, c2 = min(m, i + k + 1), min(n, j + k + 1)
answer[i][j] = summ[r2][c2] - summ[r1][c2] - summ[r2][c1] + summ[r1][c1]
return answerclass Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
int[][] sum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = mat[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
}
int[][] answer = 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, i + k + 1), c2 = Math.min(n, j + k + 1);
answer[i][j] = sum[r2][c2] - sum[r1][c2] - sum[r2][c1] + sum[r1][c1];
}
}
return answer;
}
}#include <vector>
using namespace std;
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> sum(m+1, vector<int>(n+1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sum[i][j] = mat[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
vector<vector<int>> answer(m, vector<int>(n));
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, i+k+1), c2 = min(n, j+k+1);
answer[i][j] = sum[r2][c2] - sum[r1][c2] - sum[r2][c1] + sum[r1][c1];
}
}
return answer;
}var matrixBlockSum = function(mat, k) {
const m = mat.length, n = mat[0].length;
const sum = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
sum[i][j] = mat[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
const answer = Array.from({ length: m }, () => Array(n));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const r1 = Math.max(0, i - k), c1 = Math.max(0, j - k);
const r2 = Math.min(m, i + k + 1), c2 = Math.min(n, j + k + 1);
answer[i][j] = sum[r2][c2] - sum[r1][c2] - sum[r2][c1] + sum[r1][c1];
}
}
return answer;
};#include <stdio.h>
int** matrixBlockSum(int** mat, int matSize, int* matColSize, int k, int** returnSize, int** returnColumnSizes) {
int m = matSize, n = matColSize[0];
int** summ = (int**)malloc((m+1) * sizeof(int*));
for (int i = 0; i <= m; ++i) {
summ[i] = (int*)calloc((n+1), sizeof(int));
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
summ[i][j] = mat[i-1][j-1] + summ[i-1][j] + summ[i][j-1] - summ[i-1][j-1];
}
}
int** answer = (int**)malloc(m * sizeof(int*));
for (int i = 0; i < m; ++i) {
answer[i] = (int*)malloc(n * sizeof(int));
for (int j = 0; j < n; ++j) {
int r1 = (i - k < 0) ? 0 : i - k;
int c1 = (j - k < 0) ? 0 : j - k;
int r2 = (i+k >= m) ? m-1 : i + k;
int c2 = (j+k >= n) ? n-1 : j + k;
answer[i][j] = summ[r2+1][c2+1] - summ[r1][c2+1] - summ[r2+1][c1] + summ[r1][c1];
}
}
*returnSize = m;
*returnColumnSizes = (int*)malloc(m * sizeof(int));
for (int i = 0; i < m; ++i) {
(*returnColumnSizes)[i] = n;
}
for (int i = 0; i <= m; ++i) {
free(summ[i]);
}
free(summ);
return answer;
}public class Solution {
public int[][] MatrixBlockSum(int[][] mat, int k) {
int m = mat.Length, n = mat[0].Length;
int[][] sum = new int[m + 1][];
for (int i = 0; i <= m; ++i) {
sum[i] = new int[n+1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
sum[i][j] = mat[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
int[][] answer = new int[m][];
for (int i = 0; i < m; ++i) {
answer[i] = new int[n];
for (int j = 0; j < n; ++j) {
int r1 = Math.Max(0, i - k);
int c1 = Math.Max(0, j - k);
int r2 = Math.Min(m, i + k + 1);
int c2 = Math.Min(n, j + k + 1);
answer[i][j] = sum[r2][c2] - sum[r1][c2] - sum[r2][c1] + sum[r1][c1];
}
}
return answer;
}
}Python code constructs prefix sums to quickly compute the sum for each desired block in constant time. This leverages cumulative sums for matrix range optimization.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 3: Two-Dimensional Prefix Sum
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.
function matrixBlockSum(mat: number[][], k: number): number[][] {
const m: number = mat.length;
const n: number = mat[0].length;
const s: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
}
}
const ans: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const x1: number = Math.max(i - k, 0);
const y1: number = Math.max(j - k, 0);
const x2: number = Math.min(m - 1, i + k);
const y2: number = Math.min(n - 1, j + k);
ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
}
}
return ans;
}func matrixBlockSum(mat [][]int, k int) [][]int {
m, n := len(mat), len(mat[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
}
for i, row := range mat {
for j, x := range row {
s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + x
}
}
ans := make([][]int, m)
for i := range ans {
ans[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
x1 := max(i-k, 0)
y1 := max(j-k, 0)
x2 := min(m-1, i+k)
y2 := min(n-1, j+k)
ans[i][j] = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(m * n * k * k). |
| Optimized Prefix Sum Approach | Time Complexity: O(m * n) |
| Two-Dimensional Prefix Sum | – |
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 |
Frequently asked questions
Is Matrix Block Sum easy or hard?
Matrix Block Sum is typically classified as a medium problem. The brute force idea is simple, but recognizing that repeated submatrix sums can be optimized with a 2D prefix sum requires familiarity with matrix preprocessing techniques.
Matrix Block Sum Python/Java solution
Most implementations first build a prefix sum matrix and then compute each cell's block sum using range queries. The same algorithm works across Python, Java, C++, and other languages with O(m*n) time and O(m*n) space complexity.
How to solve Matrix Block Sum in O(m*n)?
Precompute a 2D prefix sum matrix where each entry stores the sum from the top-left corner to the current cell. For each matrix position, determine the valid block boundaries and calculate the sum using the prefix formula. Each lookup takes O(1), so processing all cells takes O(m*n).
What is the best approach for Matrix Block Sum?
The optimal approach uses a 2D prefix sum matrix. After preprocessing cumulative sums in O(m*n) time, each block sum query can be computed in O(1) using inclusion–exclusion. This reduces the overall complexity from O(m*n*k^2) in brute force to O(m*n).
Is Matrix Block Sum asked at Google/Amazon/Meta?
Matrix range-sum problems using prefix sums frequently appear in interviews at companies like Amazon, Google, and Meta. Variants include submatrix sum queries, range updates, and 2D cumulative sum problems that test familiarity with prefix sum optimization.
What data structure is used in Matrix Block Sum?
The key structure is a 2D prefix sum matrix. It stores cumulative sums that allow constant-time retrieval of any rectangular region using the inclusion–exclusion principle. The problem also relies on standard matrix traversal and boundary handling.
What is the time complexity of Matrix Block Sum?
The brute force solution runs in O(m*n*k^2) time because each cell iterates through a (2k+1)x(2k+1) block. Using a 2D prefix sum reduces the total complexity to O(m*n) since each block sum becomes a constant-time range query after preprocessing.