Problem Breakdown
The goal is to count the number of subgrids within a larger grid that satisfy the definition of a “magic square.” A magic square has two strict requirements:
- Content: It must contain exactly the integers
1through9, each appearing once (distinct). No zeros, no duplicates, and no numbers outside this range are allowed in the subgrid. - Sum Property: The sum of every row, column, and both diagonals within that block must be equal. Given the content constraint (
1to9), the total sum is fixed at45, meaning each line (row/col/diag) must sum to exactly15.
Intuition
Since a magic square has specific properties, we can validate candidates efficiently:
- Constraints: The grid dimensions are small (), allowing an approach where every cell is visited.
- Validation Order: It is crucial to check the content (distinctness and range) before checking sums. If a subgrid contains duplicates or numbers outside
1-9, it cannot be a magic square regardless of its sum. This allows for “early pruning” inside the helper function, returningFalseimmediately upon finding an invalid value. - Sum Check: Once distinctness and range are confirmed (implying the set is
{1..9}), we only need to verify that all rows, columns, and diagonals sum to15. If they do not, it fails the magic square property.
Approach
We iterate through every possible top-left coordinate of a subgrid within the bounds of the input grid (, ). For each candidate:
- Content Validation: Extract all 9 elements into a set or check them on-the-fly to ensure they are between
1and9inclusive, and that no duplicates exist within the subgrid. If any violation occurs, discard immediately. - Sum Validation: Calculate sums for each of the three rows, three columns, and two diagonals. Verify all equal
15. Note: Since we enforced distinctness{1..9}, checking against15is mathematically sufficient to ensure equality among lines (if one row was different, another would likely be too or total sum wouldn’t match). - Counting: If both validations pass, increment the counter.
Complexity Analysis
- Time Complexity: , where is rows and is columns. We iterate through every possible top-left corner of a subgrid (). For each candidate, we perform constant work proportional to the fixed size of the magic square ( cells). Thus, it scales linearly with input dimensions.
- Space Complexity: auxiliary space. We use a set
seenwhich holds at most 9 integers and variables for sums/indices. The grid itself is not modified or cloned significantly beyond the current subgrid access.
Solution
class Solution:
def numMagicSquaresInside(self, grid):
"""
Counts the number of 3x3 magic square subgrids in a given integer grid.
A valid magic square must contain distinct numbers from 1 to 9
and have equal sums for all rows, columns, and diagonals (which implies sum=15).
"""
if not grid or len(grid) < 3:
return 0
R = len(grid)
C = len(grid[0])
count = 0
# Iterate over all possible top-left corners of a 3x3 subgrid
for r in range(R - 2):
for c in range(C - 2):
if self.is_magic_square(grid, r, c):
count += 1
return count
def is_magic_square(self, grid, start_r, start_c):
"""Helper to validate a specific 3x3 subgrid starting at (start_r, start_c)."""
seen = set()
# Check all cells for distinctness and range [1-9]
for i in range(3):
row_sum_i = 0
col_idx_offset = start_c
for j in range(3):
val = grid[start_r + i][start_c + j]
# Constraint: Must be between 1 and 9 inclusive.
if not (1 <= val <= 9) or val in seen:
return False
seen.add(val)
# If we reach here, distinctness and [1-9] are satisfied.
# Since sum(1..9) = 45, target row/col/diag sum must be 15.
for i in range(3):
if grid[start_r + i][start_c] + \
grid[start_r + i][start_c+1] + \
grid[start_r + i][start_c+2] != 15:
return False
# Check columns
for j in range(3):
s = (grid[start_r][start_c+j] +
grid[start_r+1][start_c+j] +
grid[start_r+2][start_c+j])
if s != 15: return False
# Check diagonals
d1 = grid[start_r][start_c] + \
grid[start_r+1][start_c+1] + \
grid[start_r+2][start_c+2]
d2 = grid[start_r][start_c+2] + \
grid[start_r+1][start_c+1] + \
grid[start_r+2][start_c]
if d1 != 15 or d2 != 15: return False
return True
Edge Cases Handled
- Empty/Small Grid: The main loop checks
len(grid) < 3and the range loops naturally handle grids smaller than by not entering the inner logic. - Invalid Values (0 or >9): Explicitly checked in
is_magic_square. If a value is outside[1, 9], it returnsFalseimmediately. - Duplicates: The
seenset ensures that if any number repeats within the block, validation fails. - Sum Mismatch: Even with distinct numbers
1-9, sums must equal15. If rows/cols/diagonals sum to something else (e.g., due to permutation error), it returnsFalse.