# Leetcode: Magic Squares In Grid

Magic Squares In Grid

Similar Problems:

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 an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

```Input: [[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:
438
951
276

while this one is not:
384
519
762

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

Note:

```- 1 <= grid.length <= 10
- 1 <= grid[0].length <= 10
- 0 <= grid[i][j] <= 15
```

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/magic-squares-in-grid
// Basic Ideas: One pass + hashmap
//
// The center point must be 5. The sum of each list must be 15.
//
// [[1,8,6]
//  [10,5,0]
//  [4,2,9]]
//
// Complexity: Time O(n*m), Space O(1)
func numMagicSquaresInside(grid [][]int) int {
if len(grid) < 3 { return 0 }
res := 0
for i:=1; i<len(grid)-1; i++ {
for j:=1; j<len(grid[0])-1; j++ {
if grid[i][j] == 5 {
is_ok := true
m := make([]bool, 9)
m[4] = true

for _, offset := range [][]int{[]int{-1, -1}, []int{-1, 0},
[]int{-1, 1}, []int{0, -1}} {
v1,v2 := grid[i+offset[0]][j+offset[1]], grid[i-offset[0]][j-offset[1]]
if v1<1 || v1>9 || v2<1 || v2>9 ||
v1+v2 != 10 || m[v1-1] == true || m[v2-1] == true {
is_ok = false
break
}
m[v1-1], m[v2-1] = true, true
}
if is_ok == true { res++ }
}
}
}
return res
}
```

Original URL: https://code.dennyzhang.com/magic-squares-in-grid

Connect with Denny In LinkedIn Or Slack

Share It, If You Like It.