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.

#1314

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： i - k j - k 且 (r, c) 在矩阵内。示例 1：输入： mat = [[1,2,3],[4,5,6],…

数组矩阵前缀和

题目描述

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

i - k <= r <= i + k,
j - k <= c <= j + k 且
(r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

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

lightbulb

解题思路

方法一：二维前缀和

本题属于二维前缀和模板题。

我们定义 $s[i][j]$ 表示矩阵 $mat$ 前 $i$ 行，前 $j$ 列的元素和。那么 $s[i][j]$ 的计算公式为：

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + mat[i-1][j-1]

这样我们就可以通过 $s$ 数组快速计算出任意矩形区域的元素和。

对于一个左上角坐标为 $(x_1, y_1)$ ，右下角坐标为 $(x_2, y_2)$ 的矩形区域的元素和，我们可以通过 $s$ 数组计算出来：

s[x_2+1][y_2+1] - s[x_1][y_2+1] - s[x_2+1][y_1] + s[x_1][y_1]

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1292 元素和小于等于阈值的正方形的最大边长 #1444 切披萨的方案数 #1074 元素和为目标值的子矩阵数量