#1314

Medium

LeetCode Problem Workspace

Matrix Block Sum

Compute a matrix where each cell contains the sum of all elements within k-distance blocks using prefix sums efficiently.

array matrix prefix sum

Problem Statement

Given an m x n integer matrix mat and an integer k, compute a new matrix answer where each cell answer[i][j] is the sum of all elements mat[r][c] such that r is within k rows and c is within k columns from (i, j), constrained to the matrix boundaries.

Return the resulting matrix answer after summing all valid blocks for each cell. For example, for mat = [[1,2,3],[4,5,6],[7,8,9]] with k = 1, the answer is [[12,21,16],[27,45,33],[24,39,28]].

Examples

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 details omitted.

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]]

Example details omitted.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100

Solution Approach

Naive Iteration

Loop over every cell and sum all elements within k-distance manually. This is simple but slow, O(m n k*k), and demonstrates why overlapping block sums require optimization.

2D Prefix Sum

Precompute a prefix sum matrix where sum[r][c] stores total from (0,0) to (r,c). Each block sum can then be computed in O(1) by combining relevant prefix sum values using inclusion-exclusion. This directly targets the Array plus Matrix pattern for fast lookups.

Boundary Handling

When computing block sums, carefully clip row and column indices to remain inside matrix limits. This prevents out-of-bounds errors and ensures correctness for edge and corner cells.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) with prefix sums, versus O(m n k k) for naive approach. Space complexity is O(m*n) for the prefix sum matrix, trading extra memory for fast block sum computation.

What Interviewers Usually Probe

Ask how to compute each cell sum without repeatedly iterating the same elements.
Check understanding of 2D prefix sums and inclusion-exclusion for matrix blocks.
Probe handling of matrix edges and index boundaries in the block sum.

Common Pitfalls or Variants

Common pitfalls

Naively summing blocks leads to timeouts on larger matrices.
Incorrectly handling boundaries can produce index errors or wrong sums at edges.
Forgetting to apply inclusion-exclusion when using prefix sums results in double-counted cells.

Follow-up variants

Compute maximum or average within each k-distance block instead of sum.
Extend to 3D matrices where each cell sum includes layers above and below.
Handle dynamic updates to mat with efficient recalculation of affected block sums.

FAQ

What is the main trick to efficiently solve Matrix Block Sum?

Use a 2D prefix sum matrix to compute each block sum in constant time instead of iterating over all elements repeatedly.

Can Matrix Block Sum be solved without extra space?

A purely in-place solution is complex and slower; prefix sums use extra O(m n) space to achieve O(m n) time.

How do I handle blocks that extend beyond matrix edges?

Clip row and column indices to matrix boundaries when using prefix sums to avoid out-of-bounds errors.

Does increasing k affect performance significantly?

With prefix sums, performance remains O(m*n) regardless of k, unlike naive summation where larger k increases runtime quadratically.

Which pattern does Matrix Block Sum follow in interviews?

It follows the Array plus Matrix pattern, combining matrix traversal with cumulative sum techniques for efficient block computations.

terminal

Solution

Solution 1: Two-Dimensional Prefix Sum

This problem is a template for two-dimensional prefix sum.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(mat, 1):
            for j, x in enumerate(row, 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                x1, y1 = max(i - k, 0), max(j - k, 0)
                x2, y2 = min(m - 1, i + k), 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

Continue Practicing

#1292 maximum side length of a square with sum less than or equal to threshold #1444 number of ways of cutting a pizza #1074 number of submatrices that sum to target