MediumNo. 0840

Magic Squares In Grid — LeetCode 840 Python Solution

Topics
Array, Hash Table, Math, Matrix
Reading time
5 min

The problem

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?

Example

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:

Python solution

PythonSolution
class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def check(i: int, j: int) -> int:
            if i + 3 > m or j + 3 > n:
                return 0
            s = set()
            row = [0] * 3
            col = [0] * 3
            a = b = 0
            for x in range(i, i + 3):
                for y in range(j, j + 3):
                    v = grid[x][y]
                    if v < 1 or v > 9:
                        return 0
                    s.add(v)
                    row[x - i] += v
                    col[y - j] += v
                    if x - i == y - j:
                        a += v
                    if x - i == 2 - (y - j):
                        b += v
            if len(s) != 9 or a != b:
                return 0
            if any(x != a for x in row) or any(x != a for x in col):
                return 0
            return 1

        m, n = len(grid), len(grid[0])
        return sum(check(i, j) for i in range(m) for j in range(n))

Complexity

Time
O(m × n)where m and n are the number of rows and columns of the matrix, respectively
Space · auxiliary
O(1)

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 840. Magic Squares In Grid is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
2965Find Missing and Repeated ValuesEasy
0036Valid SudokuMedium
0037Sudoku SolverHard
0073Set Matrix ZeroesMedium
0149Max Points on a LineHard
0268Missing NumberEasy

Frequently asked questions

How hard is LeetCode 840. Magic Squares In Grid?

LeetCode 840. Magic Squares In Grid is rated Medium on LeetCode.

What is the time complexity of LeetCode 840. Magic Squares In Grid?

The Python solution on this page runs in O(m × n), where m and n are the number of rows and columns of the matrix, respectively.

What is the space complexity of LeetCode 840. Magic Squares In Grid?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 840. Magic Squares In Grid cover?

LeetCode 840. Magic Squares In Grid is tagged Array, Hash Table, Math and Matrix on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.