⚡Flashcard Drill➔
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

  1. Enumerate every 3x3 window whose top-left corner is (i, j) for i in [0, row-3] and j in [0, col-3].
  2. 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.
  3. Verify that the nine cells are exactly the distinct values 1 through 9; this single check rules out out-of-range values and duplicates at once.
  4. 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, 15 or 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems