# Magic Squares In Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/magic-squares-in-grid)
Canonical: https://scaleengineer.com/dsa/problems/magic-squares-in-grid
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Hash Table, Matrix
---
## 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?

Note: while a magic square can only contain numbers from 1 to 9, `grid` may contain numbers up to 15.

**Example 1:**

![](https://assets.glich.co/dsa/magic-squares-in-grid/image0.jpg) 

**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:
![](https://assets.glich.co/dsa/magic-squares-in-grid/image1.jpg)
while this one is not:
![](https://assets.glich.co/dsa/magic-squares-in-grid/image2.jpg)
In total, there is only one magic square inside the given grid.

**Example 2:**

**Input:** grid = [[8]]
**Output:** 0

**Constraints:**

* `row == grid.length`
* `col == grid[i].length`
* `1 <= row, col <= 10`
* `0 <= grid[i][j] <= 15`

# Approaches
## Brute-Force Validation of All Subgrids
This approach iterates through every possible 3x3 subgrid in the input grid. For each subgrid, it performs a comprehensive check to see if it satisfies all the properties of a magic square.
**Time:** O(R * C), where R is the number of rows and C is the number of columns. We iterate through approximately R * C subgrids, and the check for each is a constant time operation (O(1) since it's always 3x3). · **Space:** O(1). The extra space used is a constant-size array for checking distinctness, which does not depend on the input grid size.
**Pros:** Simple and direct implementation of the problem definition.; Easy to understand and verify its correctness.
**Cons:** Inefficient as it performs a full, expensive check on every single 3x3 subgrid.; It doesn't leverage any specific properties of magic squares for optimization.
### Explanation
The algorithm iterates through the main grid with nested loops, considering each cell `(r, c)` as a potential top-left corner of a 3x3 subgrid. This is possible for `r` from 0 to `rows-3` and `c` from 0 to `cols-3`.

A helper function, `isMagic(grid, r, c)`, is called for each subgrid. This function validates two main properties:
1.  **Distinct Numbers from 1 to 9**: It checks if all 9 numbers in the subgrid are unique and fall within the required range of 1 to 9. This can be done using a frequency array or a set. If any number is out of range or duplicated, the subgrid is not magic.
2.  **Constant Sum**: It verifies that the sum of numbers in each of the three rows, three columns, and both main diagonals is equal to the magic constant, which is 15 for numbers 1-9.

A counter is maintained and incremented for every subgrid that passes all these checks.

```java
class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        if (rows < 3 || cols < 3) {
            return 0;
        }
        int count = 0;
        for (int r = 0; r <= rows - 3; r++) {
            for (int c = 0; c <= cols - 3; c++) {
                if (isMagic(grid, r, c)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isMagic(int[][] grid, int r, int c) {
        // 1. Check for distinct numbers 1-9
        int[] seen = new int[16];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int val = grid[r + i][c + j];
                if (val < 1 || val > 9 || seen[val] > 0) {
                    return false;
                }
                seen[val]++;
            }
        }

        // 2. Check sums
        int row1 = grid[r][c] + grid[r][c+1] + grid[r][c+2];
        int row2 = grid[r+1][c] + grid[r+1][c+1] + grid[r+1][c+2];
        int row3 = grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2];
        int col1 = grid[r][c] + grid[r+1][c] + grid[r+2][c];
        int col2 = grid[r][c+1] + grid[r+1][c+1] + grid[r+2][c+1];
        int col3 = grid[r][c+2] + grid[r+1][c+2] + grid[r+2][c+2];
        int diag1 = grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2];
        int diag2 = grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c];

        return row1 == 15 && row2 == 15 && row3 == 15 &&
               col1 == 15 && col2 == 15 && col3 == 15 &&
               diag1 == 15 && diag2 == 15;
    }
}
```
### Algorithm
- Initialize a counter `magic_squares_count` to 0.
- If the grid dimensions are smaller than 3x3, return 0.
- Iterate through each row `r` from 0 to `grid.length - 3`.
-   Inside this loop, iterate through each column `c` from 0 to `grid[0].length - 3`.
-   For the 3x3 subgrid starting at `(r, c)`, call a helper function `isMagic`.
-   The `isMagic` helper function performs the following checks:
    -   Verify that all 9 elements are distinct numbers from 1 to 9. A frequency array can be used for this.
    -   Calculate the sum of each of the 3 rows, 3 columns, and 2 diagonals.
    -   Return `true` if all 8 sums are equal to 15, otherwise return `false`.
-   If `isMagic` returns `true`, increment `magic_squares_count`.
- After the loops complete, return `magic_squares_count`.

## Optimized Brute-Force with Center Element Check
This approach significantly optimizes the brute-force method by first applying a quick filter. A fundamental property of a 3x3 magic square (using numbers 1-9) is that its center element must always be 5. By checking this condition first, we can avoid the expensive full validation for a majority of subgrids.
**Time:** O(R * C). The worst-case complexity remains the same, but the average-case performance is much better because the expensive `isMagic` function is called only when the center element is 5. · **Space:** O(1). The space usage is constant as it does not depend on the input size.
**Pros:** Much more efficient on average than the naive brute-force approach.; Simple yet powerful optimization based on a key mathematical property.
**Cons:** The worst-case time complexity is technically the same as the unoptimized version (e.g., for a grid filled with 5s).
### Explanation
The algorithm iterates through all potential 3x3 subgrids, just like the brute-force approach. However, for each subgrid, before performing the full validation, it checks if the center element `grid[r+1][c+1]` is equal to 5.

If the center element is not 5, the subgrid cannot be a magic square, and the algorithm immediately moves to the next subgrid, skipping the costly checks. Only if the center element is 5 does the algorithm proceed to the full validation. This pre-check drastically reduces the number of full validations needed, leading to a much faster average-case runtime.

```java
class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        if (rows < 3 || cols < 3) {
            return 0;
        }
        int count = 0;
        for (int r = 0; r <= rows - 3; r++) {
            for (int c = 0; c <= cols - 3; c++) {
                // Optimization: center must be 5
                if (grid[r + 1][c + 1] == 5) {
                    if (isMagic(grid, r, c)) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private boolean isMagic(int[][] grid, int r, int c) {
        // A more compact way to check distinctness and sums.
        // We already know the center is 5.
        int[] seen = new int[10];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int val = grid[r + i][c + j];
                if (val < 1 || val > 9 || seen[val] > 0) return false;
                seen[val] = 1;
            }
        }

        if (grid[r][c] + grid[r][c+1] + grid[r][c+2] != 15) return false;
        if (grid[r+1][c] + grid[r+1][c+1] + grid[r+1][c+2] != 15) return false;
        if (grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2] != 15) return false;
        if (grid[r][c] + grid[r+1][c] + grid[r+2][c] != 15) return false;
        if (grid[r][c+1] + grid[r+1][c+1] + grid[r+2][c+1] != 15) return false;
        if (grid[r][c+2] + grid[r+1][c+2] + grid[r+2][c+2] != 15) return false;
        if (grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2] != 15) return false;
        if (grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c] != 15) return false;
        
        return true;
    }
}
```
### Algorithm
- Initialize `magic_squares_count` to 0.
- If the grid dimensions are smaller than 3x3, return 0.
- Iterate through each row `r` from 0 to `grid.length - 3`.
-   Inside this loop, iterate through each column `c` from 0 to `grid[0].length - 3`.
-   **Optimization**: Check if the center element of the subgrid, `grid[r+1][c+1]`, is 5.
-   If it is not 5, `continue` to the next iteration, skipping the current subgrid.
-   If the center is 5, call the `isMagic` helper function to perform the full validation (check distinct numbers 1-9 and all 8 sums are 15).
-   If `isMagic` returns `true`, increment `magic_squares_count`.
- After the loops complete, return `magic_squares_count`.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] grid;
public
  int numMagicSquaresInside(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans += check(i, j);
      }
    }
    return ans;
  }
private
  int check(int i, int j) {
    if (i + 3 > m || j + 3 > n) {
      return 0;
    }
    int[] cnt = new int[16];
    int[] row = new int[3];
    int[] col = new int[3];
    int a = 0, b = 0;
    for (int x = i; x < i + 3; ++x) {
      for (int y = j; y < j + 3; ++y) {
        int v = grid[x][y];
        if (v < 1 || v > 9 || ++cnt[v] > 1) {
          return 0;
        }
        row[x - i] += v;
        col[y - j] += v;
        if (x - i == y - j) {
          a += v;
        }
        if (x - i + y - j == 2) {
          b += v;
        }
      }
    }
    if (a != b) {
      return 0;
    }
    for (int k = 0; k < 3; ++k) {
      if (row[k] != a || col[k] != a) {
        return 0;
      }
    }
    return 1;
  }
}

```

### JavaScript

```javascript
function numMagicSquaresInside ( grid ) { const m = grid . length ; const n = grid [ 0 ]. length ; const check = ( i , j ) => { if ( i + 3 > m || j + 3 > n ) { return 0 ; } const cnt = Array ( 16 ). fill ( 0 ); const row = Array ( 3 ). fill ( 0 ); const col = Array ( 3 ). fill ( 0 ); let [ a , b ] = [ 0 , 0 ]; for ( let x = i ; x < i + 3 ; ++ x ) { for ( let y = j ; y < j + 3 ; ++ y ) { const v = grid [ x ][ y ]; if ( v < 1 || v > 9 || ++ cnt [ v ] > 1 ) { return 0 ; } row [ x - i ] += v ; col [ y - j ] += v ; if ( x - i === y - j ) { a += v ; } if ( x - i === 2 - ( y - j )) { b += v ; } } } if ( a !== b ) { return 0 ; } for ( let k = 0 ; k < 3 ; ++ k ) { if ( row [ k ] !== a || col [ k ] !== a ) { return 0 ; } } return 1 ; }; let ans = 0 ; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { ans += check ( i , j ); } } return ans ; }
```

### CPP

```cpp
class Solution {
public:
  int numMagicSquaresInside(vector<vector<int>> &grid) {
    int m = grid.size();
    int n = grid[0].size();
    int ans = 0;
    auto check = [&](int i, int j) {
      if (i + 3 > m || j + 3 > n) {
        return 0;
      }
      vector<int> cnt(16);
      vector<int> row(3);
      vector<int> col(3);
      int a = 0, b = 0;
      for (int x = i; x < i + 3; ++x) {
        for (int y = j; y < j + 3; ++y) {
          int v = grid[x][y];
          if (v < 1 || v > 9 || ++cnt[v] > 1) {
            return 0;
          }
          row[x - i] += v;
          col[y - j] += v;
          if (x - i == y - j) {
            a += v;
          }
          if (x - i + y - j == 2) {
            b += v;
          }
        }
      }
      if (a != b) {
        return 0;
      }
      for (int k = 0; k < 3; ++k) {
        if (row[k] != a || col[k] != a) {
          return 0;
        }
      }
      return 1;
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans += check(i, j);
      }
    }
    return ans;
  }
};

```

### Python

```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))

```