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.

&nbsp;
Example 1:

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:

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


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 50
	1 &lt;= grid[i][j] &lt;= 106


class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0]) # dimensions 
        rows = [[0]*(n+1) for _ in range(m)] # prefix sum along row
        cols = [[0]*n for _ in range(m+1)] # prefix sum along column
        
        for i in range(m):
            for j in range(n): 
                rows[i][j+1] = grid[i][j] + rows[i][j]
                cols[i+1][j] = grid[i][j] + cols[i][j]
        
        ans = 1
        for i in range(m): 
            for j in range(n): 
                diag = grid[i][j]
                for k in range(min(i, j)): 
                    ii, jj = i-k-1, j-k-1
                    diag += grid[ii][jj]
                    ss = {diag}
                    for r in range(ii, i+1): ss.add(rows[r][j+1] - rows[r][jj])
                    for c in range(jj, j+1): ss.add(cols[i+1][c] - cols[ii][c])
                    ss.add(sum(grid[ii+kk][j-kk] for kk in range(k+2))) # anti-diagonal
                    if len(ss) == 1: ans = max(ans, k+2)
        return ans 
class Solution {
  public int largestMagicSquare(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    // every row prefix sum
    int[][] rowPrefix = new int[m][n];
    for (int i = 0; i < m; i++) {
      rowPrefix[i][0] = grid[i][0];
      for (int j = 1; j < n; j++) {
        rowPrefix[i][j] = rowPrefix[i][j - 1] + grid[i][j];
      }
    }

    // every column prefix sum
    int[][] columnPrefix = new int[m][n];
    for (int i = 0; i < n; i++) {
      columnPrefix[0][i] = grid[0][i];
      for (int j = 1; j < m; j++) {
        columnPrefix[j][i] = columnPrefix[j - 1][i] + grid[j][i];
      }
    }

    int result = 1;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // length of square
        int l = Math.min(m - i, n - j);
        // only check square's length is better than previous result
        for (int k = l; k > result; k--) {
          if (magic(i, j, k, grid, rowPrefix, columnPrefix)) {
            result = k;
            break;
          }
        }
      }
    }
    return result;
  }

  private boolean magic(
      int i, int j, int l, int[][] grid, int[][] rowPrefix, int[][] columnPrefix) {
    // check every row
    int target = rowPrefix[i][j + l - 1] - rowPrefix[i][j] + grid[i][j];
    for (int k = 0; k < l; k++) {
      if (rowPrefix[i + k][j + l - 1] - rowPrefix[i + k][j] + grid[i + k][j] != target) {
        return false;
      }
    }

    // check every column
    for (int k = 0; k < l; k++) {
      if (columnPrefix[i + l - 1][j + k] - columnPrefix[i][j + k] + grid[i][j + k] != target) {
        return false;
      }
    }

    // check both diagonal
    int diagonal = 0;
    // \
    // \
    for (int k = 0; k < l; k++) {
      diagonal += grid[i + k][j + k];
    }

    if (diagonal != target) {
      return false;
    }

    // /
    // /
    for (int k = 0; k < l; k++) {
      diagonal -= grid[i + l - 1 - k][j + k];
    }

    return diagonal == 0;
  }
}
class Solution {
public:
    bool isValid(int r1, int r2, int c1, int c2, vector<vector<int>>& grid, vector<vector<int>>& rg, vector<vector<int>>& cg,int checkSum){
        //Checking all row sums between top and bottom row
        for(int i = r1 + 1; i<r2; i++){
            int sum = rg[i][c2];
            if(c1>0)sum-=rg[i][c1-1];
            if(sum!=checkSum)return false;
        }
        //Checking all columns between left and right column 
        for(int j = c1 + 1; j<c2; j++){
            int sum = cg[r2][j];
            if(r1>0)sum-=cg[r1-1][j];
            if(sum!=checkSum)return false;
        }
        int sum = 0;
        //right diagonal
        for(int i = r1, j = c1; i<=r2&&j<=c2; i++, j++){
            sum+=grid[i][j];
        }
        if(sum!=checkSum)return false;
        sum = 0;
        //left diagonal
        for(int i = r1, j = c2; i<=r2&&j>=c1; i++, j--){
            sum+=grid[i][j];
        }
        if(sum!=checkSum)return false;
        return true;
    }
    int largestMagicSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>>rg, cg;
        rg = grid;
        cg = grid;
        //Generating row prefix sum matrix
        for(int i = 0; i<m; i++){
            for(int j = 1; j<n; j++){
                rg[i][j] += rg[i][j-1];
            }
        }
        //Generating column prefix sum matrix
        for(int j = 0; j<n; j++){
            for(int i = 1; i<m; i++){
                cg[i][j] += cg[i-1][j];
            }
        }
        int ans = 1;
        //For each cell in the loop, we find the larget magic square with cell {i,j} at the top left corner.
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(m-i<=ans)return ans;//The largest square with it's top row as i will have at max a dimension = m-i, and in case are answer is already >= this dimension, we can simply return our answer
                //Pruning step -->
                //We only need to consider squares whose sizes our greater than our current answer, so we prune our search by starting from squares having side-lengths greater than ans.
                int r = i + ans;
                int c = j + ans;
                while(r<m&&c<n){
                    //For a square having it's 4 corners defined by {i,j,r,c}, we calculate the sum of all these 4 sides, and call our isValid function in case these sums are equal
                    int rsum1 = j>0 ? rg[i][c] - rg[i][j-1] : rg[i][c];//top row sum
                    int csum1 = i>0 ? cg[r][j] - cg[i-1][j] : cg[r][j];//left column sum
                    int rsum2 = j>0 ? rg[r][c] - rg[r][j-1] : rg[r][c];//bottom row sum
                    int csum2 = i>0 ? cg[r][c] - cg[i-1][c] : cg[r][c];//right column sum
                    if(rsum1==csum2&&rsum2==csum2&&isValid(i,r,j,c,grid, rg, cg, rsum1)){
                        ans = max(ans, r-i+1);
                    }
                    r++;
                    c++;
                }
            }
        }
        return ans;
    }
};
var largestMagicSquare = function(grid) {
   const row = grid.length;
   const col = grid[0].length;
   const startSize = row <= col ? row : col;
   for(let s = startSize; s > 1; s--){
       for(let r = 0; r < grid.length - s + 1; r++){
           for(let c = 0; c < grid[0].length - s + 1; c++){
               if(isMagic(grid, r, c, s)){
                   return s;
               }
           }
       }
   }
   return 1;
};

const isMagic = (grid, i, j, size) => {
   let targetSum = 0;
   for(let c = j; c < j + size; c++){
       targetSum += grid[i][c];
   }
   //check rows
   for(let r = i; r < i + size; r++){
       let sum = 0;
       for(let c = j; c < j + size; c++){
           sum += grid[r][c];
       }
       if(targetSum !== sum){
           return false;
       }
   }
   //check cols
   for(let c = j; c < j + size; c++){
       let sum = 0;
       for(let r = i; r < i + size; r++){
           sum += grid[r][c];
       }
       if(targetSum !== sum){
           return false;
       }
   }
   //check diagonals
   let diagSum = 0, antiDiagSum = 0;
   for(let c = 0; c < size; c++){
       diagSum += grid[i + c][j+c];
       antiDiagSum += grid[i + c][j + size - 1 - c];
   }
   if(diagSum !== antiDiagSum || diagSum !== targetSum){
       return false
   }
   return true;
}
Largest Magic Square