# 1895. Largest Magic Square

• Time: $O(mnk^2)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 class Solution { public: int largestMagicSquare(vector>& grid) { const int m = grid.size(); const int n = grid[0].size(); // prefixRow[i][j] := prefix sum of first j nums in i-th row vector> prefixRow(m, vector(n + 1)); // prefixCol[i][j] := prefix sum of first j nums in i-th col vector> prefixCol(n, vector(m + 1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { prefixRow[i][j + 1] = prefixRow[i][j] + grid[i][j]; prefixCol[j][i + 1] = prefixCol[j][i] + grid[i][j]; } for (int k = min(m, n); k >= 2; --k) if (containsMagicSquare(grid, prefixRow, prefixCol, k)) return k; return 1; } private: // Returns true if grid contains any magic square of size k x k. bool containsMagicSquare(const vector>& grid, const vector>& prefixRow, const vector>& prefixCol, int k) { for (int i = 0; i + k - 1 < grid.size(); ++i) for (int j = 0; j + k - 1 < grid[0].size(); ++j) if (isMagicSquare(grid, prefixRow, prefixCol, i, j, k)) return true; return false; } // Returns true if grid[i..i + k)[j..j + k) is a magic square. bool isMagicSquare(const vector>& grid, const vector>& prefixRow, const vector>& prefixCol, int i, int j, int k) { int diag = 0; int antiDiag = 0; for (int d = 0; d < k; ++d) { diag += grid[i + d][j + d]; antiDiag += grid[i + d][j + k - 1 - d]; } if (diag != antiDiag) return false; for (int d = 0; d < k; ++d) { if (getSum(prefixRow, i + d, j, j + k - 1) != diag) return false; if (getSum(prefixCol, j + d, i, i + k - 1) != diag) return false; } return true; } // Returns sum(grid[i][l..r]) or sum(grid[l..r][i]). int getSum(const vector>& prefix, int i, int l, int r) { return prefix[i][r + 1] - prefix[i][l]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class Solution { public int largestMagicSquare(int[][] grid) { final int m = grid.length; final int n = grid[0].length; // prefixRow[i][j] := prefix sum of first j nums in i-th row int[][] prefixRow = new int[m][n + 1]; // prefixCol[i][j] := prefix sum of first j nums in i-th col int[][] prefixCol = new int[n][m + 1]; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { prefixRow[i][j + 1] = prefixRow[i][j] + grid[i][j]; prefixCol[j][i + 1] = prefixCol[j][i] + grid[i][j]; } for (int k = Math.min(m, n); k >= 2; --k) if (containsMagicSquare(grid, prefixRow, prefixCol, k)) return k; return 1; } // Returns true if grid contains a magic square of size k x k. private boolean containsMagicSquare(int[][] grid, int[][] prefixRow, int[][] prefixCol, int k) { for (int i = 0; i + k - 1 < grid.length; ++i) for (int j = 0; j + k - 1 < grid[0].length; ++j) if (isMagicSquare(grid, prefixRow, prefixCol, i, j, k)) return true; return false; } // Returns true if grid[i..i + k)[j..j + k) is a magic square. private boolean isMagicSquare(int[][] grid, int[][] prefixRow, int[][] prefixCol, int i, int j, int k) { int diag = 0; int antiDiag = 0; for (int d = 0; d < k; ++d) { diag += grid[i + d][j + d]; antiDiag += grid[i + d][j + k - 1 - d]; } if (diag != antiDiag) return false; for (int d = 0; d < k; ++d) { if (getSum(prefixRow, i + d, j, j + k - 1) != diag) return false; if (getSum(prefixCol, j + d, i, i + k - 1) != diag) return false; } return true; } // Returns sum(grid[i][l..r]) or sum(grid[l..r][i]). private int getSum(int[][] prefix, int i, int l, int r) { return prefix[i][r + 1] - prefix[i][l]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 class Solution: def largestMagicSquare(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) # prefixRow[i][j] := prefix sum of first j nums in i-th row prefixRow = [[0] * (n + 1) for _ in range(m)] # prefixCol[i][j] := prefix sum of first j nums in i-th col prefixCol = [[0] * (m + 1) for _ in range(n)] for i in range(m): for j in range(n): prefixRow[i][j + 1] = prefixRow[i][j] + grid[i][j] prefixCol[j][i + 1] = prefixCol[j][i] + grid[i][j] # Returns true if grid[i..i + k)[j..j + k) is a magic square. def isMagicSquare(i: int, j: int, k: int) -> bool: diag, antiDiag = 0, 0 for d in range(k): diag += grid[i + d][j + d] antiDiag += grid[i + d][j + k - 1 - d] if diag != antiDiag: return False for d in range(k): if self._getSum(prefixRow, i + d, j, j + k - 1) != diag: return False if self._getSum(prefixCol, j + d, i, i + k - 1) != diag: return False return True # Returns true if grid contains a magic square of size k x k. def containsMagicSquare(k: int) -> bool: for i in range(m - k + 1): for j in range(n - k + 1): if isMagicSquare(i, j, k): return True return False for k in range(min(m, n), 1, -1): if containsMagicSquare(k): return k return 1 # Returns sum(grid[i][l..r]) or sum(grid[l..r][i]). def _getSum(self, prefix: List[List[int]], i: int, l: int, r: int) -> int: return prefix[i][r + 1] - prefix[i][l]