Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 840 with 13 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 840 # by problem number
lcpy gen -s magic_squares_in_grid # by problem name
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.
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.
Input: grid = [[8]]
Output: 0
class Solution:
# Time: O(rows * cols)
# Space: O(1)
def num_magic_squares_inside(self, grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
def is_magic(r: int, c: int) -> bool:
# A 3x3 magic square over 1..9 always has center 5 and sum 15
if grid[r + 1][c + 1] != 5:
return False
vals = [grid[r + i][c + j] for i in range(3) for j in range(3)]
if sorted(vals) != list(range(1, 10)):
return False
if any(sum(grid[r + i][c : c + 3]) != 15 for i in range(3)):
return False
if any(sum(grid[r + i][c + j] for i in range(3)) != 15 for j in range(3)):
return False
return (
grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] == 15
and grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] == 15
)
return sum(is_magic(r, c) for r in range(rows - 2) for c in range(cols - 2))
| Time | Space |
|---|---|
| O(rows * cols) | O(1) |