NeetCode #900LC-840MediumMath & Geometry
← Back to All Problems#900 · #840 · Magic Squares In Grid(矩阵中的幻方)
📌 Problem Statement & Constraints
A 3x3 magic square contains each of the integers
1 to 9 exactly once, and every row, every column and both diagonals sum to the same value. Given a row x col grid of integers, return the number of 3x3 subgrids that are magic squares. Constraints: 1 <= row, col <= 10, 0 <= grid[i][j] <= 15.💡 Core Algorithmic Approaches
- Enumerate every 3x3 window whose top-left corner is
(i, j)foriin[0, row-3]andjin[0, col-3]. - Apply a cheap necessary check first: the centre of any 3x3 magic square must be
5, so windows with a different centre are rejected immediately. - Verify that the nine cells are exactly the distinct values
1through9; this single check rules out out-of-range values and duplicates at once. - Finally check that all three rows, all three columns and both diagonals sum to the same value, which for the 1..9 square is necessarily
15.
💻 Benchmark Python3 Implementation
class Solution:
def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
if m < 3 or n < 3:
return 0
count = 0
for i in range(m - 2):
for j in range(n - 2):
if grid[i + 1][j + 1] != 5: # centre must be 5
continue
seen = set()
ok = True
for a in range(3):
for b in range(3):
v = grid[i + a][j + b]
if v < 1 or v > 9 or v in seen:
ok = False
break
seen.add(v)
if not ok:
break
if not ok:
continue
s = grid[i][j] + grid[i][j + 1] + grid[i][j + 2]
for a in range(3): # rows
if grid[i + a][j] + grid[i + a][j + 1] + grid[i + a][j + 2] != s:
ok = False
break
if not ok:
continue
for b in range(3): # columns
if grid[i][j + b] + grid[i + 1][j + b] + grid[i + 2][j + b] != s:
ok = False
break
if not ok:
continue
if grid[i][j] + grid[i + 1][j + 1] + grid[i + 2][j + 2] != s:
continue # main diagonal
if grid[i][j + 2] + grid[i + 1][j + 1] + grid[i + 2][j] != s:
continue # anti-diagonal
count += 1
return count⚡ Complexity Deep Dive
⏱️ Time Complexity
O(row * col): at most 64 windows, each validated in constant time.
💾 Space Complexity
O(1) beyond the seen set, which holds at most nine values.
⚠️ Interview Pitfalls & Follow-ups
- Skipping the distinctness and range check: a window containing
0,15or a repeated value can still satisfy the sum conditions but is not magic. - Checking only rows and columns: both diagonals must also sum to the magic constant.
- Treating the centre-5 check as sufficient: it is only a fast rejection; the full validation is still required.
- Off-by-one in the window loop: the last valid top-left corner is
(row - 3, col - 3).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.