Magic Squares In Grid — LeetCode 840 Python Solution
MediumArrayHash TableMathMatrix
- Problem
- #840
- Pattern
- Matrix and Grid
- Reading time
- 5 min
- Source
- leetcode.com
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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(m \times n), where m and n are the number of rows and columns of the matrix, respectively |
| Space | O(1) auxiliary |
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
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 \times 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.