# 840. Magic Squares In Grid
###### tags: `leetcode` `840` `medium` `rewrite`

## :memo: Question


## :memo: 題意
* 給你一個矩陣，然後要你找出 magic square，magic square 的定義是在 3 * 3 矩陣內有 1 ~ 9 的數字，且所有的 rows 和 cols 和對角的數字加起來的總和是一樣的（如下圖 紅色 藍色 橘色的線上的數字總和要一樣）。

## :memo: leetcode solution
* :medal: **思考一**: 那這樣 magic square 每行每列數字的總和應該是固定的，因為九宮格裡只有 1 ~ 9 的數字，所以數字的總和要是15 。
* :medal: **思考二**: 暴力解。

## :memo: leetcode solution code

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        
        if m < 3 or n < 3:
            return 0
        
        
        def helper(x, y, m, n):
            if x <= m - 3 and y <= n - 3:
                g = [grid[k][y:y+3] for k in range(x,x+3)]
                if set([g[i][j] for i in range(3) for j in range(3)]) == {1,2,3,4,5,6,7,8,9}:
                    rows = list(map(sum, g))
                    cols = list(map(sum, zip(*g)))
                    diag = [g[0][0]+g[1][1]+g[2][2], g[2][0]+g[1][1]+g[0][2]]
                    if set(rows+cols+diag) == {15}:
                        return True
            return False
            
        
        ans = 0
        
        for x in range(m):
            for y in range(n):
                if helper(x, y, m, n):
                    ans +=1
        
        return ans

## :memo: BigO
* 時間複雜度: O((m-3)* (n-3)) 就是 O(m * n)。
* 空間複雜度: O(3* 3)，因為每檢查一次都要暫存 3 * 3 矩陣。