1895. Largest Magic Square
Approach
Precompute row and diagonal prefix sums; check all submatrices for equal row/col/diagonal sums.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.
// Approach: Precompute row and diagonal prefix sums; check all submatrices for equal row/col/diagonal sums.
// Time: O(mn * min(m,n)) Space: O(mn)
public class Solution
{
public int LargestMagicSquare(int[][] grid)
{
int m = grid.Length;
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][];
for (int i = 0; i < m; i++)
prefixRow[i] = new int[n + 1];
// prefixCol[i][j] := the sum of the first j numbers in the i-th column
int[][] prefixCol = new int[n][];
for (int i = 0; i < n; i++)
prefixCol[i] = new 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 = 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 bool 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 bool 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];
}
}