Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The candidate size is fixed at nine cells, so it is simplest to check the definition directly for each possible 3-by-3 window. Equal sums alone are insufficient: the cells must also be exactly the distinct digits one through nine.

Approach

Enumerate every window by its bottom-right corner, beginning at row and column two. Smaller grids produce no candidates.
Collect the nine values in a set and reject duplicates.
Compare the two diagonal sums, then require each of the three row sums and three column sums to equal that same value.
Require the collected values to be exactly one through nine, excluding otherwise well-formed windows containing zero or larger values.
Count every window passing all checks; overlapping magic squares are separate valid subgrids.

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        res = 0

        def valid(i, j):
            nums = set()

            for k in range(i - 2, i + 1):
                for l in range(j - 2, j + 1):
                    if grid[k][l] in nums: return False
                    nums.add(grid[k][l])
            
            sd1 = grid[i - 2][j - 2] + grid[i - 1][j - 1] + grid[i][j]
            sd2 = grid[i - 2][j] + grid[i - 1][j - 1] + grid[i][j - 2]
            if sd1 != sd2: return False

            for r in range(i - 2, i + 1):
                if grid[r][j - 2] + grid[r][j - 1] + grid[r][j] != sd1: return False
            
            for c in range(j - 2, j + 1):
                if grid[i - 2][c] + grid[i - 1][c] + grid[i][c] != sd1: return False
            
            return nums == set(range(1, 10))
        
        for i in range(2, n):
            for j in range(2, m):
                if valid(i, j): res += 1
        
        return res

Complexity analysis

For an R × C grid, there are O(RC) candidate 3 × 3 windows and each performs a fixed amount of work. Time is O(RC) and auxiliary space is O(1) because each temporary set contains at most nine values.