Skip to content

870. Magic Squares In Grid

Array Hash Table Math Matrix

Problem - Magic Squares In Grid

Medium

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?

Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.

 

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

 

Constraints:

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def checker(i, j):
            if i + 3 > m or j + 3 > n:
                return 0
            set_vals = set()
            row = [0] * 3
            col = [0] * 3
            a = b = 0
            for x in range(i, i + 3):
                for y in range(j, j + 3):
                    val = grid[x][y]
                    if val < 1 or val > 9:
                        return 0
                    set_vals.add(val)
                    row[x - i] += val
                    col[y - j] += val
                    if x - i == y - j:
                        a += val
                    if x - i == 2 - y + j:
                        b += val

            if len(set_vals) != 9 or a != b:
                return 0
            if any(val != a for val in row) or any(val != a for val in col):
                return 0
            return 1

        return sum(checker(i, j) for i in range(m) for j in range(n))

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.1 MB (100.00%)