Skip to main content
Talentd

Matrix Block Sum - Solution & Explanation

MediumArrayMatrixPrefix Sum20 min readAsked at: Meta, Visa, Google
Practice this problem

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.length
  • n == mat[i].length
  • 1 <= m, n, k <= 100
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) for prefix sum computation and submatrix retrieval.
Space Complexity: O(m * n) for auxiliary storage.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1) as we're utilizing an extra matrix of the same size.

Optimized Prefix Sum Approach

Time Complexity: O(m * n) for prefix sum computation and submatrix retrieval.
Space Complexity: O(m * n) for auxiliary storage.

Two-Dimensional Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Block TraversalO(m * n * k²)O(1)Small matrices or small k where performance is not critical
2D Prefix SumO(m * n)O(m * n)General case and interview settings with frequent submatrix sum queries

Video Solution

1314. Matrix Block Sum | LEETCODE MEDIUM | DYNAMIC PROGRAMMING | CODE EXPLAINER • code Explainer • 10,293 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Matrix Block Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Neighbor Sum Service

Next

Maximum Sum of an Hourglass