# Largest Magic Square
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-magic-square)
Canonical: https://scaleengineer.com/dsa/problems/largest-magic-square
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
**Companies:** [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## Problem
A `k x k` **magic square** is a `k x k` grid filled with integers such that every row sum, every column sum, and both diagonal sums are **all equal**. The integers in the magic square **do not have to be distinct**. Every `1 x 1` grid is trivially a **magic square**.

Given an `m x n` integer `grid`, return _the **size** (i.e., the side length_ `k`_) of the **largest magic square** that can be found within this grid_.

**Example 1:**

![](https://assets.glich.co/dsa/largest-magic-square/image0.jpg) 

**Input:** grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
**Output:** 3
**Explanation:** The largest magic square has a size of 3.
Every row sum, column sum, and diagonal sum of this magic square is equal to 12.
- Row sums: 5+1+6 = 5+4+3 = 2+7+3 = 12
- Column sums: 5+5+2 = 1+4+7 = 6+3+3 = 12
- Diagonal sums: 5+4+3 = 6+4+2 = 12

**Example 2:**

![](https://assets.glich.co/dsa/largest-magic-square/image1.jpg) 

**Input:** grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
**Output:** 2

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 50`
* `1 <= grid[i][j] <= 106`

# Approaches
## Brute-Force Iteration
This approach involves a straightforward, exhaustive search. It checks every possible square subgrid within the given `m x n` grid to see if it qualifies as a magic square. To find the largest one, we start by checking for the largest possible square size and progressively decrease the size until a magic square is found.
**Time:** O(m * n * min(m, n)^3). Let `L = min(m, n)`. There are three nested loops for `k`, `r`, and `c`, giving `O(L * m * n)` iterations. Inside, the `isMagic` check takes `O(k^2)` time as it computes `~2k` sums, each taking `O(k)` time. This results in an overall complexity of roughly `O(m * n * L^3)`, or `O(N^5)` if `m` and `n` are similar. · **Space:** O(1) extra space. The algorithm only uses a few variables to store sums during the check, not dependent on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space, operating in-place on the input grid.
**Cons:** Highly inefficient due to redundant calculations of sums for overlapping subgrids.; Likely to result in a 'Time Limit Exceeded' error for larger grid sizes within the given constraints.
### Explanation
The algorithm iterates through all possible side lengths `k` for a square, starting from `min(m, n)` down to 2. A size of 1 is the base case, as any 1x1 grid is a magic square. For each size `k`, we check every possible `k x k` subgrid. A subgrid is defined by its top-left corner `(r, c)`. For each subgrid, we verify the magic square property: all row sums, column sums, and the two diagonal sums must be equal. This is done by first calculating a `target_sum` (e.g., the sum of the main diagonal) and then calculating and comparing all other `2k+1` sums against it. Each sum calculation involves a loop of `k` elements. If a magic square of size `k` is found, we can immediately return `k` because we are searching in decreasing order of size. If no magic square larger than 1x1 is found, the function returns 1.

```java
class Solution {
    public int largestMagicSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int k = Math.min(m, n); k >= 2; k--) {
            for (int r = 0; r <= m - k; r++) {
                for (int c = 0; c <= n - k; c++) {
                    if (isMagic(grid, r, c, k)) {
                        return k;
                    }
                }
            }
        }
        return 1;
    }

    private boolean isMagic(int[][] grid, int r, int c, int k) {
        long diag1Sum = 0;
        for (int i = 0; i < k; i++) {
            diag1Sum += grid[r + i][c + i];
        }

        long diag2Sum = 0;
        for (int i = 0; i < k; i++) {
            diag2Sum += grid[r + i][c + k - 1 - i];
        }
        if (diag1Sum != diag2Sum) {
            return false;
        }

        for (int i = 0; i < k; i++) {
            long rowSum = 0;
            for (int j = 0; j < k; j++) {
                rowSum += grid[r + i][c + j];
            }
            if (rowSum != diag1Sum) {
                return false;
            }
        }

        for (int j = 0; j < k; j++) {
            long colSum = 0;
            for (int i = 0; i < k; i++) {
                colSum += grid[r + i][c + j];
            }
            if (colSum != diag1Sum) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Iterate through all possible side lengths `k` for a square, starting from the maximum possible size, `min(m, n)`, down to 2.
- For each size `k`, iterate through all possible top-left corners `(r, c)` of a `k x k` subgrid.
- For each subgrid, call a helper function `isMagic(r, c, k)` to verify if it's a magic square.
- The `isMagic` function calculates the sum of all rows, all columns, and both diagonals of the subgrid. It first computes a target sum (e.g., from the main diagonal) and then compares all other `2k+1` sums to this target. Each sum calculation requires iterating through `k` elements.
- If all sums are equal, a magic square of size `k` is found. Since we are iterating `k` downwards, this is the largest possible magic square, and we can immediately return `k`.
- If the loops complete without finding any magic square of size 2 or greater, return 1.

## Optimized Approach using Prefix Sums
This approach significantly optimizes the brute-force method by using a dynamic programming technique known as prefix sums (or integral images). By pre-calculating the sums of all row and column prefixes, we can find the sum of any row or column segment in constant `O(1)` time. This drastically speeds up the process of checking if a subgrid is a magic square.
**Time:** O(m * n * min(m, n)^2). Preprocessing takes `O(m * n)`. The main loops iterate `O(m * n * L)` times, where `L = min(m, n)`. The check for a `k x k` subgrid takes `O(k)` time. The total time is roughly `O(m * n * L^2)`, or `O(N^4)` if `m` and `n` are similar. · **Space:** O(m * n) to store the two prefix sum matrices. Each matrix has a size comparable to the input grid.
**Pros:** Significantly more efficient than the brute-force approach.; Passes within typical time limits for the given constraints.
**Cons:** Requires additional space proportional to the size of the grid to store the prefix sum matrices.
### Explanation
The main bottleneck in the brute-force approach is the repeated calculation of row and column sums. This can be optimized by pre-computation. We create two matrices, `rowPrefixSum` and `colPrefixSum`, to store these cumulative sums. `rowPrefixSum[i][c+1]` holds the sum `grid[i][0] + ... + grid[i][c]`, and `colPrefixSum[r+1][j]` holds `grid[0][j] + ... + grid[r][j]`. These can be built in `O(m*n)` time.

With these structures, the sum of a row segment `grid[r][c...c+k-1]` is simply `rowPrefixSum[r][c+k] - rowPrefixSum[r][c]`, an `O(1)` operation. The same applies to column sums.

The overall structure of iterating from the largest possible size `k` downwards remains. However, the check for each subgrid becomes much faster. While diagonal sums still take `O(k)` to compute, checking all `k` row sums and `k` column sums now takes a total of `O(k)` time instead of `O(k^2)`. This reduces the complexity of checking a single subgrid from `O(k^2)` to `O(k)`, leading to a substantial overall performance gain.

```java
class Solution {
    public int largestMagicSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        long[][] rowPrefixSum = new long[m][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowPrefixSum[i][j + 1] = rowPrefixSum[i][j] + grid[i][j];
            }
        }

        long[][] colPrefixSum = new long[m + 1][n];
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colPrefixSum[i + 1][j] = colPrefixSum[i][j] + grid[i][j];
            }
        }

        for (int k = Math.min(m, n); k >= 2; k--) {
            for (int r = 0; r <= m - k; r++) {
                for (int c = 0; c <= n - k; c++) {
                    if (isMagic(grid, r, c, k, rowPrefixSum, colPrefixSum)) {
                        return k;
                    }
                }
            }
        }
        return 1;
    }

    private boolean isMagic(int[][] grid, int r, int c, int k, long[][] rowPrefixSum, long[][] colPrefixSum) {
        long diag1Sum = 0;
        for (int i = 0; i < k; i++) {
            diag1Sum += grid[r + i][c + i];
        }

        long diag2Sum = 0;
        for (int i = 0; i < k; i++) {
            diag2Sum += grid[r + i][c + k - 1 - i];
        }
        if (diag1Sum != diag2Sum) {
            return false;
        }

        for (int i = 0; i < k; i++) {
            long rowSum = rowPrefixSum[r + i][c + k] - rowPrefixSum[r + i][c];
            if (rowSum != diag1Sum) {
                return false;
            }
        }

        for (int j = 0; j < k; j++) {
            long colSum = colPrefixSum[r + k][c + j] - colPrefixSum[r][c + j];
            if (colSum != diag1Sum) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- First, pre-calculate prefix sums for all rows and columns of the grid. Create two auxiliary matrices: `rowPrefixSum` and `colPrefixSum`.
- `rowPrefixSum[i][j]` will store the sum of elements in `grid[i]` from column 0 to `j-1`.
- `colPrefixSum[i][j]` will store the sum of elements in `grid`'s column `j` from row 0 to `i-1`.
- This preprocessing step takes `O(m * n)` time.
- Then, iterate `k` from `min(m, n)` down to 2.
- For each `k`, iterate through all top-left corners `(r, c)`.
- For each subgrid, check if it's a magic square:
  - Calculate the main and anti-diagonal sums in `O(k)` time.
  - Use the pre-calculated prefix sum matrices to find each of the `k` row sums and `k` column sums in `O(1)` time per sum.
  - Compare all sums. If they are equal, return `k`.
- If the loops finish, return 1.

# Solutions
### Java

```java
class Solution { private int [][] rowsum ; private int [][] colsum ; public int largestMagicSquare ( int [][] grid ) { int m = grid . length , n = grid [ 0 ]. length ; rowsum = new int [ m + 1 ][ n + 1 ]; colsum = new int [ m + 1 ][ n + 1 ]; for ( int i = 1 ; i <= m ; ++ i ) { for ( int j = 1 ; j <= n ; ++ j ) { rowsum [ i ][ j ] = rowsum [ i ][ j - 1 ] + grid [ i - 1 ][ j - 1 ]; colsum [ i ][ j ] = colsum [ i - 1 ][ j ] + grid [ i - 1 ][ j - 1 ]; } } for ( int k = Math . min ( m , n ); k > 1 ; -- k ) { for ( int i = 0 ; i + k - 1 < m ; ++ i ) { for ( int j = 0 ; j + k - 1 < n ; ++ j ) { int i2 = i + k - 1 , j2 = j + k - 1 ; if ( check ( grid , i , j , i2 , j2 )) { return k ; } } } } return 1 ; } private boolean check ( int [][] grid , int x1 , int y1 , int x2 , int y2 ) { int val = rowsum [ x1 + 1 ][ y2 + 1 ] - rowsum [ x1 + 1 ][ y1 ]; for ( int i = x1 + 1 ; i <= x2 ; ++ i ) { if ( rowsum [ i + 1 ][ y2 + 1 ] - rowsum [ i + 1 ][ y1 ] != val ) { return false ; } } for ( int j = y1 ; j <= y2 ; ++ j ) { if ( colsum [ x2 + 1 ][ j + 1 ] - colsum [ x1 ][ j + 1 ] != val ) { return false ; } } int s = 0 ; for ( int i = x1 , j = y1 ; i <= x2 ; ++ i , ++ j ) { s += grid [ i ][ j ]; } if ( s != val ) { return false ; } s = 0 ; for ( int i = x1 , j = y2 ; i <= x2 ; ++ i , -- j ) { s += grid [ i ][ j ]; } if ( s != val ) { return false ; } return true ; } }
```

### CPP

```cpp
class Solution {
public:
  int largestMagicSquare(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid.size();
    vector<vector<int>> rowsum(m + 1, vector<int>(n + 1));
    vector<vector<int>> colsum(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1];
        colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1];
      }
    }
    for (int k = min(m, n); k > 1; --k) {
      for (int i = 0; i + k - 1 < m; ++i) {
        for (int j = 0; j + k - 1 < n; ++j) {
          int i2 = i + k - 1, j2 = j + k - 1;
          if (check(grid, rowsum, colsum, i, j, i2, j2))
            return k;
        }
      }
    }
    return 1;
  }
  bool check(vector<vector<int>> &grid, vector<vector<int>> &rowsum,
             vector<vector<int>> &colsum, int x1, int y1, int x2, int y2) {
    int val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1];
    for (int i = x1 + 1; i <= x2; ++i)
      if (rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val)
        return false;
    for (int j = y1; j <= y2; ++j)
      if (colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val)
        return false;
    int s = 0;
    for (int i = x1, j = y1; i <= x2; ++i, ++j)
      s += grid[i][j];
    if (s != val)
      return false;
    s = 0;
    for (int i = x1, j = y2; i <= x2; ++i, --j)
      s += grid[i][j];
    if (s != val)
      return false;
    return true;
  }
};

```

### Python

```python
class Solution : def largestMagicSquare ( self , grid : List [ List [ int ]]) -> int : m , n = len ( grid ), len ( grid [ 0 ]) rowsum = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] colsum = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] for i in range ( 1 , m + 1 ): for j in range ( 1 , n + 1 ): rowsum [ i ][ j ] = rowsum [ i ][ j - 1 ] + grid [ i - 1 ][ j - 1 ] colsum [ i ][ j ] = colsum [ i - 1 ][ j ] + grid [ i - 1 ][ j - 1 ] def check ( x1 , y1 , x2 , y2 ): val = rowsum [ x1 + 1 ][ y2 + 1 ] - rowsum [ x1 + 1 ][ y1 ] for i in range ( x1 + 1 , x2 + 1 ): if rowsum [ i + 1 ][ y2 + 1 ] - rowsum [ i + 1 ][ y1 ] != val : return False for j in range ( y1 , y2 + 1 ): if colsum [ x2 + 1 ][ j + 1 ] - colsum [ x1 ][ j + 1 ] != val : return False s , i , j = 0 , x1 , y1 while i <= x2 : s += grid [ i ][ j ] i += 1 j += 1 if s != val : return False s , i , j = 0 , x1 , y2 while i <= x2 : s += grid [ i ][ j ] i += 1 j -= 1 if s != val : return False return True for k in range ( min ( m , n ), 1 , - 1 ): i = 0 while i + k - 1 < m : j = 0 while j + k - 1 < n : i2 , j2 = i + k - 1 , j + k - 1 if check ( i , j , i2 , j2 ): return k j += 1 i += 1 return 1
```