# 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:

| Rule | Meaning |
|---|---|
| Size | The subgrid is exactly `3 x 3` |
| Values | It contains distinct numbers from `1` to `9` |
| Rows | Every row has the same sum |
| Columns | Every column has the same sum |
| Diagonals | Both diagonals have the same sum |

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

| Item | Meaning |
|---|---|
| Input | A 2D integer matrix `grid` |
| Output | Number of `3 x 3` magic square subgrids |
| Subgrid | Must be contiguous |
| Valid values | Exactly the numbers `1` through `9` |
| Required sum | Each row, column, and diagonal must have the same sum |

Function shape:

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

## Examples

Example 1:

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

The left `3 x 3` subgrid is:

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

Its rows sum to:

```python
15, 15, 15
```

Its columns sum to:

```python
15, 15, 15
```

Its diagonals sum to:

```python
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:

```python
1
```

Example 2:

```python
grid = [[8]]
```

There is no `3 x 3` subgrid.

So the answer is:

```python
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:

```python
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:

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

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

```python
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:

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

The values are:

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

They are exactly the numbers `1` through `9`.

Rows:

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

Columns:

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

Diagonals:

```python
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:

```python
R = number of rows
C = number of columns
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(R * C)` | Each possible `3 x 3` subgrid is checked in constant time |
| Space | `O(1)` | The seen set has at most `9` values |

## Implementation

```python
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:

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

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

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

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

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

Then we check all row sums:

```python
if row_sum != 15:
    return False
```

Then all column sums:

```python
if col_sum != 15:
    return False
```

Finally, both diagonals must also equal `15`:

```python
return diagonal_1 == 15 and diagonal_2 == 15
```

The outer loops try every possible `3 x 3` position:

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

If the subgrid is magic, we increment the answer.

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard example | Confirms one valid subgrid inside a larger grid |
| Grid smaller than `3 x 3` | Confirms no candidate subgrid exists |
| Exact magic square | Confirms direct valid case |
| Duplicate value | Confirms distinctness check |
| Value outside `1` to `9` | Confirms range check |