Largest Magic Square — Solution in Python, Java & C++
Largest Magic Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Largest Magic Square is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A k x k magic square is a square block of numbers in which every row sum, every column sum and both diagonal sums are all equal. The numbers need not be distinct, and every 1 x 1 block is trivially a magic square.
Given an m x n integer matrix grid, return the side length k of the largest magic square that appears as a contiguous k x k sub-grid of grid.
Example 1
Input: grid = [[3,8,1,6],[1,3,5,7],[2,4,9,2]]
Output: 3
Explanation: Columns 1–3 hold the classic 3 × 3 magic square: every row, column and diagonal sums to 15.
Example 2
Input: grid = [[5,1,3],[2,3,3],[1,3,3]]
Output: 2
Explanation: The bottom-right block `[[3,3],[3,3]]` is magic; the whole grid is not.
Example 3
Input: grid = [[1,2],[3,4]]
Output: 1
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 10^6
Hints for Largest Magic Square
Hint 1
Try sizes from largest to smallest; the first size that has a magic square anywhere is the answer, and size 1 always works.
Hint 2
Prefix sums along every row and every column turn each row or column sum of a block into one subtraction.
Hint 3
For a candidate block, compare all
krow sums andkcolumn sums with the first row's sum, then compute the two diagonals directly.
How to solve Largest Magic Square
Check every block, largest sizes first, with row and column prefix sums making each line sum O(1).
Approach
- Build
rowP[i][j]= sum ofgrid[i][0..j-1]andcolP[i][j]= sum ofgrid[0..i-1][j]. - For
kfrommin(m, n)down to 2, for every top-left(r, c)with the block inside the grid: - Let
targetbe the block's first row sum. Every row sumrowP[r+t][c+k] - rowP[r+t][c]and column sumcolP[r+k][c+t] - colP[r][c+t]must equal it; stop early on a mismatch. - Add up both diagonals directly; if they also equal
target, returnk. - If no block of size 2 or more is magic, return 1.
Why it works
The search is exhaustive over sizes and positions, and it checks exactly the definition: all rows, all columns and both diagonals of the block have one common sum. Scanning sizes downwards means the first hit is the largest.
Complexity
- Time —
O(m · n · min(m, n)²) - Space —
O(m · n)
Pitfalls
- Both diagonals must match, not just the rows and columns.
- Every
1 x 1block is magic, so the answer is at least 1. - Values reach 10^6 and a line has up to 50 of them — 5 × 10^7 still fits in 32 bits.
Reference solution
Python
from typing import List
def largestMagicSquare(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
row_p = [[0] * (n + 1) for _ in range(m)]
col_p = [[0] * n for _ in range(m + 1)]
for i in range(m):
for j in range(n):
row_p[i][j + 1] = row_p[i][j] + grid[i][j]
col_p[i + 1][j] = col_p[i][j] + grid[i][j]
for k in range(min(m, n), 1, -1):
for r in range(m - k + 1):
for c in range(n - k + 1):
target = row_p[r][c + k] - row_p[r][c]
ok = True
for t in range(k):
if row_p[r + t][c + k] - row_p[r + t][c] != target or col_p[r + k][c + t] - col_p[r][c + t] != target:
ok = False
break
if not ok:
continue
d1 = sum(grid[r + t][c + t] for t in range(k))
d2 = sum(grid[r + t][c + k - 1 - t] for t in range(k))
if d1 == target and d2 == target:
return k
return 1Java
public static int largestMagicSquare(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] rowP = new int[m][n + 1], colP = new int[m + 1][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
rowP[i][j + 1] = rowP[i][j] + grid[i][j];
colP[i + 1][j] = colP[i][j] + grid[i][j];
}
}
for (int k = Math.min(m, n); k >= 2; k--) {
for (int r = 0; r + k <= m; r++) {
for (int c = 0; c + k <= n; c++) {
int target = rowP[r][c + k] - rowP[r][c];
boolean ok = true;
for (int t = 0; t < k && ok; t++) {
if (rowP[r + t][c + k] - rowP[r + t][c] != target) ok = false;
else if (colP[r + k][c + t] - colP[r][c + t] != target) ok = false;
}
if (!ok) continue;
int d1 = 0, d2 = 0;
for (int u = 0; u < k; u++) { d1 += grid[r + u][c + u]; d2 += grid[r + u][c + k - 1 - u]; }
if (d1 == target && d2 == target) return k;
}
}
}
return 1;
}C++
int largestMagicSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> rowP(m, vector<int>(n + 1, 0)), colP(m + 1, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
rowP[i][j + 1] = rowP[i][j] + grid[i][j];
colP[i + 1][j] = colP[i][j] + grid[i][j];
}
}
for (int k = min(m, n); k >= 2; k--) {
for (int r = 0; r + k <= m; r++) {
for (int c = 0; c + k <= n; c++) {
int target = rowP[r][c + k] - rowP[r][c];
bool ok = true;
for (int t = 0; t < k && ok; t++) {
if (rowP[r + t][c + k] - rowP[r + t][c] != target) ok = false;
else if (colP[r + k][c + t] - colP[r][c + t] != target) ok = false;
}
if (!ok) continue;
int d1 = 0, d2 = 0;
for (int u = 0; u < k; u++) { d1 += grid[r + u][c + u]; d2 += grid[r + u][c + k - 1 - u]; }
if (d1 == target && d2 == target) return k;
}
}
}
return 1;
}JavaScript
var largestMagicSquare = function(grid) {
var m = grid.length, n = grid[0].length, i, j;
var rowP = [], colP = [];
for (i = 0; i < m; i++) rowP.push(new Array(n + 1).fill(0));
for (i = 0; i <= m; i++) colP.push(new Array(n).fill(0));
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
rowP[i][j + 1] = rowP[i][j] + grid[i][j];
colP[i + 1][j] = colP[i][j] + grid[i][j];
}
}
for (var k = Math.min(m, n); k >= 2; k--) {
for (var r = 0; r + k <= m; r++) {
for (var c = 0; c + k <= n; c++) {
var target = rowP[r][c + k] - rowP[r][c], ok = true;
for (var t = 0; t < k && ok; t++) {
if (rowP[r + t][c + k] - rowP[r + t][c] !== target) ok = false;
else if (colP[r + k][c + t] - colP[r][c + t] !== target) ok = false;
}
if (!ok) continue;
var d1 = 0, d2 = 0;
for (var u = 0; u < k; u++) { d1 += grid[r + u][c + u]; d2 += grid[r + u][c + k - 1 - u]; }
if (d1 === target && d2 === target) return k;
}
}
}
return 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal