You are given a 2D grid of integers, grid, with m rows and n columns. A magic square is a square subgrid where the sums of every row, every column, and both diagonals are all equal.
Your task is to find the size (side length) of the largest magic square that can be found anywhere in grid. The square must be entirely within the grid, and every element of the square is used exactly once in its corresponding row, column, and diagonal sums.
grid.At first glance, it seems we could check every possible square subgrid, and for each, verify if it's a magic square by checking all its rows, columns, and diagonals. However, this brute-force approach would be far too slow for large grids, as the number of possible squares and the checks required for each grow quickly.
To optimize, we want to reduce repeated work. Since checking sums of rows and columns is a common operation, we can precompute prefix sums for rows and columns. This way, we can quickly calculate the sum of any row or column in constant time. For diagonals, since they are less regular, we can also precompute diagonal prefix sums.
The main challenge is efficiently checking, for every possible square of size k (from largest to smallest), whether all its rows, columns, and diagonals sum to the same value. By starting from the largest possible size and stopping at the first valid magic square, we ensure we find the largest one.
This approach ensures that we efficiently check all possible magic squares, prioritizing larger sizes and minimizing redundant computation.
Suppose grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]].
[[1,4,5],[5,1,6],[5,4,3]]
[[5,1],[5,4]]
[[4,3],[7,3]]
[[7,1],[2,5]]
To find the largest magic square in a grid, we precompute prefix sums for rows, columns, and diagonals to enable fast sum checks. We then examine all possible square sizes and positions, using the prefix sums to verify magic square properties efficiently. This approach is significantly more efficient than brute-force and leverages dynamic programming concepts for optimal performance.
class Solution:
def largestMagicSquare(self, grid):
m, n = len(grid), len(grid[0])
# Prefix sums for rows and columns
row_psum = [[0]*(n+1) for _ in range(m)]
col_psum = [[0]*(n) for _ in range(m+1)]
for i in range(m):
for j in range(n):
row_psum[i][j+1] = row_psum[i][j] + grid[i][j]
col_psum[i+1][j] = col_psum[i][j] + grid[i][j]
# Prefix sums for diagonals
diag1 = [[0]*(n+1) for _ in range(m+1)] # top-left to bottom-right
diag2 = [[0]*(n+2) for _ in range(m+1)] # top-right to bottom-left (1-based for easier indexing)
for i in range(m):
for j in range(n):
diag1[i+1][j+1] = diag1[i][j] + grid[i][j]
diag2[i+1][j] = diag2[i][j+1] + grid[i][j]
for k in range(min(m, n), 0, -1):
for i in range(m-k+1):
for j in range(n-k+1):
s = row_psum[i][j+k] - row_psum[i][j]
ok = True
# Check all rows
for r in range(i, i+k):
if row_psum[r][j+k] - row_psum[r][j] != s:
ok = False
break
if not ok:
continue
# Check all columns
for c in range(j, j+k):
if col_psum[i+k][c] - col_psum[i][c] != s:
ok = False
break
if not ok:
continue
# Check main diagonal
if diag1[i+k][j+k] - diag1[i][j] != s:
continue
# Check anti-diagonal
if diag2[i+k][j] - diag2[i][j+k] != s:
continue
return k
return 1
class Solution {
public:
int largestMagicSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> row_psum(m, vector<int>(n+1, 0)), col_psum(m+1, vector<int>(n, 0));
vector<vector<int>> diag1(m+1, vector<int>(n+1, 0)), diag2(m+1, vector<int>(n+2, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
row_psum[i][j+1] = row_psum[i][j] + grid[i][j];
col_psum[i+1][j] = col_psum[i][j] + grid[i][j];
diag1[i+1][j+1] = diag1[i][j] + grid[i][j];
diag2[i+1][j] = diag2[i][j+1] + grid[i][j];
}
}
for (int k = min(m, n); k >= 1; --k) {
for (int i = 0; i + k <= m; ++i) {
for (int j = 0; j + k <= n; ++j) {
int s = row_psum[i][j+k] - row_psum[i][j];
bool ok = true;
// Check rows
for (int r = i; r < i + k; ++r) {
if (row_psum[r][j+k] - row_psum[r][j] != s) {
ok = false;
break;
}
}
if (!ok) continue;
// Check columns
for (int c = j; c < j + k; ++c) {
if (col_psum[i+k][c] - col_psum[i][c] != s) {
ok = false;
break;
}
}
if (!ok) continue;
// Main diagonal
if (diag1[i+k][j+k] - diag1[i][j] != s) continue;
// Anti-diagonal
if (diag2[i+k][j] - diag2[i][j+k] != s) continue;
return k;
}
}
}
return 1;
}
};
class Solution {
public int largestMagicSquare(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] row_psum = new int[m][n+1];
int[][] col_psum = new int[m+1][n];
int[][] diag1 = new int[m+1][n+1];
int[][] diag2 = new int[m+1][n+2];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
row_psum[i][j+1] = row_psum[i][j] + grid[i][j];
col_psum[i+1][j] = col_psum[i][j] + grid[i][j];
diag1[i+1][j+1] = diag1[i][j] + grid[i][j];
diag2[i+1][j] = diag2[i][j+1] + grid[i][j];
}
}
for (int k = Math.min(m, n); k >= 1; --k) {
for (int i = 0; i + k <= m; ++i) {
for (int j = 0; j + k <= n; ++j) {
int s = row_psum[i][j+k] - row_psum[i][j];
boolean ok = true;
// Check rows
for (int r = i; r < i + k; ++r) {
if (row_psum[r][j+k] - row_psum[r][j] != s) {
ok = false;
break;
}
}
if (!ok) continue;
// Check columns
for (int c = j; c < j + k; ++c) {
if (col_psum[i+k][c] - col_psum[i][c] != s) {
ok = false;
break;
}
}
if (!ok) continue;
// Main diagonal
if (diag1[i+k][j+k] - diag1[i][j] != s) continue;
// Anti-diagonal
if (diag2[i+k][j] - diag2[i][j+k] != s) continue;
return k;
}
}
}
return 1;
}
}
var largestMagicSquare = function(grid) {
const m = grid.length, n = grid[0].length;
const row_psum = Array.from({length: m}, () => Array(n+1).fill(0));
const col_psum = Array.from({length: m+1}, () => Array(n).fill(0));
const diag1 = Array.from({length: m+1}, () => Array(n+1).fill(0));
const diag2 = Array.from({length: m+1}, () => Array(n+2).fill(0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
row_psum[i][j+1] = row_psum[i][j] + grid[i][j];
col_psum[i+1][j] = col_psum[i][j] + grid[i][j];
diag1[i+1][j+1] = diag1[i][j] + grid[i][j];
diag2[i+1][j] = diag2[i][j+1] + grid[i][j];
}
}
for (let k = Math.min(m, n); k >= 1; --k) {
for (let i = 0; i + k <= m; ++i) {
for (let j = 0; j + k <= n; ++j) {
let s = row_psum[i][j+k] - row_psum[i][j];
let ok = true;
// Check rows
for (let r = i; r < i + k; ++r) {
if (row_psum[r][j+k] - row_psum[r][j] !== s) {
ok = false;
break;
}
}
if (!ok) continue;
// Check columns
for (let c = j; c < j + k; ++c) {
if (col_psum[i+k][c] - col_psum[i][c] !== s) {
ok = false;
break;
}
}
if (!ok) continue;
// Main diagonal
if (diag1[i+k][j+k] - diag1[i][j] !== s) continue;
// Anti-diagonal
if (diag2[i+k][j] - diag2[i][j+k] !== s) continue;
return k;
}
}
}
return 1;
};