Magic Squares In Grid

main.md

Question

Approach

I slide a 3×3 window over every possible position in the grid and check whether that 3×3 subgrid forms a valid magic square. For each subgrid, I first extract its nine numbers and make sure they are exactly the distinct integers from 1 to 9, since a magic square cannot contain anything else. If that condition fails, I skip it immediately. Otherwise, I compute the sums of its three rows, three columns, and the two diagonals. If all eight of these sums are equal, then the subgrid satisfies the magic square property, so I count it. I repeat this for every valid 3×3 starting position and finally return the total count.

Implementation

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        ans = 0
        
        def is_magic(r, c):
            vals = [grid[r+i][c+j] for i in range(3) for j in range(3)]
            
            if sorted(vals) != list(range(1, 10)):
                return False
            
            row_sums = [sum(grid[r+i][c:c+3]) for i in range(3)]

            col_sums = [grid[r][c+j] + grid[r+1][c+j] + grid[r+2][c+j] for j in range(3)]

            d1 = grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2]
            d2 = grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c]
            
            all_sums = row_sums + col_sums + [d1, d2]
            return len(set(all_sums)) == 1
        
        for i in range(rows - 3 + 1):
            for j in range(cols - 3 + 1):
                if is_magic(i, j):
                    ans += 1
        
        return ans

Complexities

• Time: O((m−2)(n−2))
• Space: O(1)