0840.Magic Squares In Grid

• Link: 840. Magic Squares In Grid - Medium
• Track: NeetCode150

Question

Restate the problem

• Given a rows x cols grid of integers
• Count how many 3 x 3 subgrids are magic squares
• A magic square means:
  • It contains all numbers from 1 to 9 exactly once
  • Every row, every column, and both diagonals have the same sum

Edge Case

• Grid smaller than 3 x 3 → return 0
• A 3 x 3 subgrid contains duplicate numbers → not a magic square

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Brute force (check every 3 x 3 box)	$O(m\cdot n)$	$O(1)$

Method 1 - Brute force

Key idea:

• For any valid 3 x 3 magic square using digits 1..9 exactly once, the center must be 5, enabling early pruning.
• 对于任何一个由 1..9 恰好组成的合法 3 x 3 幻方，中心位置必须是 5，因此可以提前进行剪枝。

Approach

• Since a magic square must be exactly 3 x 3, scan every possible center cell
• For each center (r, c), collect the surrounding 3 x 3 values
• Check whether:
  1. The subgrid contains every number from 1 to 9
  2. All 3 rows have the same sum
  3. All 3 columns have the same sum
  4. Both diagonals have the same sum
• If all conditions are true, count it as one magic square

Complexity

• Time Complexity: $O(m\cdot n)$
• Space Complexity: $O(1)$

Code

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        
        def magic_square(row, col):
            val = []
            for r in [row - 1, row, row + 1]:
                for c in [col - 1, col, col + 1]:
                    val.append(grid[r][c])
 
            for idx in range(1, 10):
                if idx not in val:
                    return False
 
            total = sum(val[:3])
            # check row
            for idx in [0, 3, 6]:
                if sum(val[idx: idx+3]) != total:
                    return False
            
            # check col
            for idx in [0, 1, 2]:
                if (val[idx] + val[idx+3] + val[idx+6]) != total:
                    return False
            
            # check diagonals
            if (val[0] + val[4] + val[8]) != total:
                return False
            
            if (val[2] + val[4] + val[6]) != total:
                return False
            
            return True
        
        count = 0
        for r in range(1, rows - 1):
            for c in range(1, cols - 1):
                if grid[r][c] != 5:
                    continue
                if magic_square(r, c):
                    count += 1
        
        return count

---

Mistake

• A valid 3 x 3 magic square using 1..9 must have center 5