In this guide, you will get 1895. Largest Magic Square LeetCode Solution with the best time and space complexity. The solution to Largest Magic Square problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
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
m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 106
Complexity Analysis
Time Complexity: O(mnk^2)
Space Complexity: O(mn)
1895. Largest Magic Square LeetCode Solution in C++
class Solution {
public:
int largestMagicSquare(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
// prefixRow[i][j] := the sum of the first j numbers in the i-th row
vector<vector<int>> prefixRow(m, vector<int>(n + 1));
// prefixCol[i][j] := the sum of the first j numbers in the i-th column
vector<vector<int>> prefixCol(n, vector<int>(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 the grid contains any magic square of size k x k.
bool containsMagicSquare(const vector<vector<int>>& grid,
const vector<vector<int>>& prefixRow,
const vector<vector<int>>& 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<vector<int>>& grid,
const vector<vector<int>>& prefixRow,
const vector<vector<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]).
int getSum(const vector<vector<int>>& prefix, int i, int l, int r) {
return prefix[i][r + 1] - prefix[i][l];
}
}; /* code provided by PROGIEZ */
1895. Largest Magic Square LeetCode Solution in Java
class Solution {
public int largestMagicSquare(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
// prefixRow[i][j] := the sum of the first j numbers in the i-th row
int[][] prefixRow = new int[m][n + 1];
// prefixCol[i][j] := the sum of the first j numbers in the i-th column
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 the grid contains any 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];
}
} // code provided by PROGIEZ
1895. Largest Magic Square LeetCode Solution in Python
class Solution:
def largestMagicSquare(self, grid: list[list[int]]) -> int:
m = len(grid)
n = len(grid[0])
# prefixRow[i][j] := the sum of the first j numbers in the i-th row
prefixRow = [[0] * (n + 1) for _ in range(m)]
# prefixCol[i][j] := the sum of the first j numbers in the i-th column
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]
def isMagicSquare(i: int, j: int, k: int) -> bool:
"""Returns True if grid[i..i + k)[j..j + k) is a magic square."""
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
def containsMagicSquare(k: int) -> bool:
"""Returns True if the grid contains any magic square of size k x k."""
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
def _getSum(self, prefix: list[list[int]], i: int, l: int, r: int) -> int:
"""Returns sum(grid[i][l..r]) or sum(grid[l..r][i])."""
return prefix[i][r + 1] - prefix[i][l] # code by PROGIEZ
