What is the core pattern in Magic Squares In Grid?

The core pattern is array scanning plus hash lookup. You slide a 3x3 window across the grid, use a tiny lookup structure to confirm the digits are exactly 1 through 9, and then check the eight required line sums.

Why is the center value often useful in this problem?

In any 3x3 magic square using 1 through 9, the center must be 5. Some optimized solutions use that as an extra early filter, but it is optional because the full digit and sum validation is already constant time.

Why is the time complexity O(M \cdot N) instead of O(M \cdot N \cdot 9)?

The extra factor is absorbed into the constant because every candidate window always has exactly nine cells. In interview terms, Magic Squares In Grid is linear in the number of possible 3x3 starting positions.

Do I need a hash set if the values are only 1 through 15?

You need some constant-size uniqueness check, but it does not have to be a full hash set. A boolean array of size 10 or a bitmask is usually cleaner and faster for rejecting duplicates and out-of-range digits.

What is the most common wrong approach for LeetCode 840?

The most common mistake is checking only whether row, column, and diagonal sums match. That misses invalid windows with duplicate numbers or digits outside 1 through 9, which this problem explicitly allows in the input grid.

#840

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

矩阵中的幻方

3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。给定一个由整数组成的 row x col 的 grid ，其中有多少个 3 × 3 的 “幻方” 子矩阵？注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以…

数组哈希表数学矩阵

题目描述

3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。

给定一个由整数组成的row x col 的 grid，其中有多少个 3 × 3 的 “幻方” 子矩阵？

注意：虽然幻方只能包含 1 到 9 的数字，但 grid 可以包含最多15的数字。

示例 1：

输入: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]
输出: 1
解释: 
下面的子矩阵是一个 3 x 3 的幻方：

而这一个不是：

总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。

示例 2:

输入: grid = [[8]]
输出: 0

提示:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

lightbulb

解题思路

方法一：枚举

我们直接枚举每个 $3 \times 3$ 子矩阵的左上角坐标 $(i, j)$ ，然后判断该子矩阵是否满足“幻方矩阵”，若是，答案加一。枚举结束后，返回答案即可。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def check(i: int, j: int) -> int:
            if i + 3 > m or j + 3 > n:
                return 0
            s = set()
            row = [0] * 3
            col = [0] * 3
            a = b = 0
            for x in range(i, i + 3):
                for y in range(j, j + 3):
                    v = grid[x][y]
                    if v < 1 or v > 9:
                        return 0
                    s.add(v)
                    row[x - i] += v
                    col[y - j] += v
                    if x - i == y - j:
                        a += v
                    if x - i == 2 - (y - j):
                        b += v
            if len(s) != 9 or a != b:
                return 0
            if any(x != a for x in row) or any(x != a for x in col):
                return 0
            return 1

        m, n = len(grid), len(grid[0])
        return sum(check(i, j) for i in range(m) for j in range(n))

speed

复杂度分析

指标	值
时间	O(M \cdot N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
They want you to notice the 3x3 size is fixed, so a brute-force window scan is already optimal enough.
question_mark
They expect an early rejection step for digits outside 1 to 9 or repeated numbers before doing all sum checks.
question_mark
They may be testing whether you avoid overengineering a constant-size matrix problem with unnecessary preprocessing.

warning

常见陷阱

外企场景

error
Checking only equal row and column sums can misclassify windows that reuse digits or include values above 9.
error
Forgetting to validate both diagonals misses the classic failure case where rows and columns look consistent but the square is not magic.
error
Building a general n x n magic-square framework wastes time here because LeetCode 840 only asks for fixed 3x3 windows.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the coordinates of each magic square instead of just the count.
arrow_right_alt
Change the task to detect almost-magic 3x3 windows where exactly one line sum is wrong.
arrow_right_alt
Generalize the validator so it checks a provided k x k subgrid, which removes the constant-time advantage of this problem.

help

常见问题

外企场景

继续练习

#781 森林中的兔子 #939 最小面积矩形 #957 N 天后的牢房