LeetCode 840: Magic Squares In Grid

Problem Restatement

We are given a row x col grid of integers.

We need to count how many contiguous 3 x 3 subgrids are magic squares.

A 3 x 3 magic square must satisfy all of these rules:

The input grid may contain numbers outside 1 to 9, so those subgrids cannot be magic squares. The official constraints use 1 <= row, col <= 10 and 0 <= grid[i][j] <= 15.

Input and Output

Function shape:

class Solution:
    def numMagicSquaresInside(self, grid: list[list[int]]) -> int:
        ...

Examples

Example 1:

grid = [
    [4, 3, 8, 4],
    [9, 5, 1, 9],
    [2, 7, 6, 2],
]

The left 3 x 3 subgrid is:

[
    [4, 3, 8],
    [9, 5, 1],
    [2, 7, 6],
]

Its rows sum to:

15, 15, 15

Its columns sum to:

15, 15, 15

Its diagonals sum to:

15, 15

It also contains every number from 1 to 9 exactly once.

So it is a magic square.

The right 3 x 3 subgrid is not a magic square.

The answer is:

1

Example 2:

grid = [[8]]

There is no 3 x 3 subgrid.

So the answer is:

0

First Thought: Check Every 3 x 3 Subgrid

The grid is small, and the subgrid size is fixed.

So the natural solution is:

1. Try every possible top-left corner of a 3 x 3 subgrid.
2. Check whether that subgrid is a magic square.
3. Count the valid ones.

The top-left corner can be:

r from 0 to rows - 3
c from 0 to cols - 3

For each corner, the validation cost is constant because the subgrid always has only 9 cells.

Key Insight

A valid 3 x 3 magic square with values 1 through 9 has total sum:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

Since there are 3 rows, each row must sum to:

45 / 3 = 15

So we can check every row, column, and diagonal against 15.

We must also check distinctness and range. A subgrid with repeated values or values outside 1 to 9 cannot be valid, even if some sums look correct.

Algorithm

For each possible top-left coordinate (r, c):

1. Check all 9 cells.
2. Ensure every value is between 1 and 9.
3. Ensure no value appears twice.
4. Check the three row sums.
5. Check the three column sums.
6. Check both diagonal sums.
7. If all checks pass, count the subgrid.

Walkthrough

Use the subgrid:

[
    [4, 3, 8],
    [9, 5, 1],
    [2, 7, 6],
]

The values are:

4, 3, 8, 9, 5, 1, 2, 7, 6

They are exactly the numbers 1 through 9.

Rows:

4 + 3 + 8 = 15
9 + 5 + 1 = 15
2 + 7 + 6 = 15

Columns:

4 + 9 + 2 = 15
3 + 5 + 7 = 15
8 + 1 + 6 = 15

Diagonals:

4 + 5 + 6 = 15
8 + 5 + 2 = 15

All checks pass, so this subgrid contributes 1.

Correctness

The algorithm checks every contiguous 3 x 3 subgrid because every possible top-left corner is visited.

For each such subgrid, the validation checks exactly the definition of a 3 x 3 magic square: the cells must contain distinct values from 1 to 9, and all three rows, all three columns, and both diagonals must have the same sum.

Since the values are exactly 1 through 9, the total is 45. Therefore, if the subgrid is magic, each row and column sum must be 15. Checking against 15 is equivalent to checking that all row, column, and diagonal sums are equal.

The algorithm increments the answer only when all required conditions hold. It rejects every subgrid that violates at least one condition.

Therefore, the final count is exactly the number of magic square subgrids.

Complexity

Let:

R = number of rows
C = number of columns

Implementation

class Solution:
    def numMagicSquaresInside(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        def is_magic(r: int, c: int) -> bool:
            seen = set()

            for i in range(3):
                for j in range(3):
                    value = grid[r + i][c + j]

                    if value < 1 or value > 9:
                        return False
                    if value in seen:
                        return False

                    seen.add(value)

            for i in range(3):
                row_sum = (
                    grid[r + i][c]
                    + grid[r + i][c + 1]
                    + grid[r + i][c + 2]
                )
                if row_sum != 15:
                    return False

            for j in range(3):
                col_sum = (
                    grid[r][c + j]
                    + grid[r + 1][c + j]
                    + grid[r + 2][c + j]
                )
                if col_sum != 15:
                    return False

            diagonal_1 = grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2]
            diagonal_2 = grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c]

            return diagonal_1 == 15 and diagonal_2 == 15

        answer = 0

        for r in range(rows - 2):
            for c in range(cols - 2):
                if is_magic(r, c):
                    answer += 1

        return answer

Code Explanation

We first store the grid dimensions:

rows = len(grid)
cols = len(grid[0])

The helper function checks one 3 x 3 subgrid whose top-left corner is (r, c):

def is_magic(r: int, c: int) -> bool:

The first check verifies that the subgrid contains distinct numbers from 1 through 9:

if value < 1 or value > 9:
    return False
if value in seen:
    return False

Then we check all row sums:

if row_sum != 15:
    return False

Then all column sums:

if col_sum != 15:
    return False

Finally, both diagonals must also equal 15:

return diagonal_1 == 15 and diagonal_2 == 15

The outer loops try every possible 3 x 3 position:

for r in range(rows - 2):
    for c in range(cols - 2):

If the subgrid is magic, we increment the answer.

Testing

def run_tests():
    s = Solution()

    assert s.numMagicSquaresInside([
        [4, 3, 8, 4],
        [9, 5, 1, 9],
        [2, 7, 6, 2],
    ]) == 1

    assert s.numMagicSquaresInside([[8]]) == 0

    assert s.numMagicSquaresInside([
        [4, 3, 8],
        [9, 5, 1],
        [2, 7, 6],
    ]) == 1

    assert s.numMagicSquaresInside([
        [4, 3, 8],
        [9, 5, 1],
        [2, 7, 7],
    ]) == 0

    assert s.numMagicSquaresInside([
        [10, 3, 2],
        [1, 5, 9],
        [4, 7, 6],
    ]) == 0

    print("all tests passed")

run_tests()

Test meaning: