A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given a row x col grid of integers, how many 3 x 3 "magic square" subgrids are there?  (Each subgrid is contiguous).
 
Example 1:

Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:

while this one is not:

In total, there is only one magic square inside the given grid.

Example 2:
Input: grid = [[8]]
Output: 0

Example 3:
Input: grid = [[4,4],[3,3]]
Output: 0

Example 4:
Input: grid = [[4,7,8],[9,5,1],[2,3,6]]
Output: 0

 
Constraints:

row == grid.length
col == grid[i].length
1 <= row, col <= 10
0 <= grid[i][j] <= 15

Difficulty: interview

Starter code:

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        # slide window and call isMagicSquare
        if len(grid) < 3 or len(grid[0]) < 3:
            return 0
        rows = len(grid)
        cols = len(grid[0])
        magic_squares = 0
        for i in range(rows - 2):
            for j in range(cols - 2):
                window = [tmp[j:j + 3] for tmp in grid[i: i + 3]]
                if self.isMagicSquare(window):
                    magic_squares += 1
        
        return magic_squares
    
    def isMagicSquare(self, square: List[List[int]]) -> bool:
        target = square[0][0] + square[0][1] + square[0][2]
        seen = {}
        print(square)
        # check rows
        for row in square:
            tmp = 0
            for i in row:
                tmp += i
                if i in seen or i > 9 or i < 1:
                    return False
                else:
                    seen[i] = 1
            if tmp != target:
                return False
        
        # check cols
        for i in range(3):
            tmp = 0
            for row in square:
                tmp += row[i]
            
            if tmp != target:
                return False
        
        
        # check left to right diag
        tmp = 0
        for i in range(3):
            tmp += square[i][i]
        if tmp != target:
            return False
        
        # check right to left diag
        tmp = 0
        for i in range(3):
            tmp += square[i][2 - i]
        if tmp != target:
            return False
        
        return True

class Solution:
    
    def isMagicSquare(self, grid):
        '''
        Check whether the given grid is a magic square
        '''
        # Check the elements
        flat = [num for row in grid for num in row]
        if sorted(flat) != [1, 2, 3, 4, 5, 6, 7, 8, 9]:
            return False
        
        # Check the row, column and diagnal sums
        row_sums = [sum(row) for row in grid]
        col_sums = [sum([row[i] for row in grid]) for i in range(3)]
        diag_sums = [sum([grid[i][i] for i in range(3)]), (grid[0][2] + grid[1][1] + grid[2][0])]
        row_sums.extend(col_sums)
        row_sums.extend(diag_sums)
        return len(set(row_sums)) == 1
    
    
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        # 9:37 --> 9:52 --> 10:31 9/14/20
        cnt = 0
        # Construct the 3x3 square
        for i in range(len(grid)-2):
            for j in range(len(grid)-2):
                temp_grid = [grid[i+k][j:j+3] for k in range(3)]
                if self.isMagicSquare(temp_grid):
                    cnt += 1
        
        return cnt