Largest Magic Square solution and explanation
Google
9 more videos on this problem
Leetcode 1895. Largest Magic SquareFraz · 9:06 · 6K views
LeetCode 1895. Largest Magic SquareHappy Coding · 16:38 · 2K views
Largest Magic Square | LeetCode 1895 | Medium | Prefix Sum + Brute Force | Daily LeetCode Study Placement · 24:18 · 1K views
1895. Largest Magic Square | Leetcode Daily - PythonLeetcode Daily · 9:05 · 1K views
1895. Largest Magic Square (Leetcode Medium)Programming Live with Larry · 1:02:26 · 642 views
Daily Leetcode #2119: Jan 18, 2026 - 1895. Largest Magic SquareProgramming Live with Larry · 35:21 · 434 views
Largest Magic Square | LeetCode 1895 - Pythonimpoldev · 22:27 · 249 views
Largest Magic Square | LeetCode 1895 | Prefix SumcodeTips · 19:44 · 220 views
Largest Magic Square | LeetCode 1895 | Java Code | Developer CoderDeveloper Coder · 24:45 · 181 views
LeetCode Daily Challenge | Largest Magic Square (1895) | Brute Force Explained | C++The Boolean Brain · 21:19 · 175 views
The problem
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
Example 2:
Input: grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]] Output: 2
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 106
Approach overview
Problem Overview: Given a grid of integers, find the size of the largest k x k subgrid where every row sum, column sum, and both diagonal sums are equal. Such a subgrid is called a magic square. The task is to scan the matrix and return the maximum possible k.
Approach 1: Brute Force with Prefix Sums (Time: O(m * n * k^2), Space: O(m * n))
Start by computing prefix sums for rows and columns so you can query the sum of any row segment or column segment in constant time. For every possible top-left corner in the matrix, try every possible square size k. For each candidate square, check all k row sums and k column sums using the prefix arrays, and compute the two diagonals directly. If every sum matches the first row's sum, the square is magic. This approach is straightforward and easier to reason about, but verifying all rows and columns for every candidate square introduces an extra k factor.
Prefix sums are the key helper here. A row prefix array lets you compute sum(row, c1..c2) instantly, while a column prefix array provides sum(col, r1..r2). That avoids recomputing sums repeatedly and significantly reduces the naive O(k^3) checks. This technique is common in problems involving repeated range queries on arrays and grids.
Approach 2: Optimized Prefix Sum Verification (Time: O(m * n * min(m,n)), Space: O(m * n))
This approach still relies on prefix sums but reduces unnecessary checks. Precompute row and column prefix sums once. Then iterate over possible square sizes from largest to smallest. For each size k, scan all valid top-left positions. Compute the target sum from the first row of the square. Next verify columns using prefix sums and compute the two diagonals directly. Because you attempt larger squares first, you can return immediately once a valid magic square is found.
The optimization works because prefix sums reduce every row and column verification to O(1). The algorithm effectively checks each candidate square in linear time relative to its size rather than quadratic. Combined with early termination when a valid square appears, this performs well even for larger grids.
Recommended for interviews: The optimized prefix sum approach is what most interviewers expect. The brute force version shows that you understand how to enumerate candidate squares and validate sums. Adding prefix sums and checking larger squares first demonstrates practical optimization skills and familiarity with common grid techniques.
Approach 1: Brute Force with Prefix Sums
This approach involves iterating through possible top-left corners of squares and testing every possible size of squares beginning from that point. For each square, it computes row sums, column sums, and diagonal sums, comparing them to check if they form a magic square. Using prefix sums helps in reducing the time complexity when calculating sums of rows and columns.
def largestMagicSquare(grid):
m, n = len(grid), len(grid[0])
for size in range(min(m, n), 0, -1):
for i in range(m - size + 1):
for j in range(n - size + 1):
if isMagicSquare(grid, i, j, size):
return size
return 1
def isMagicSquare(grid, r, c, k):
expected = sum(grid[r][c:c + k])
for i in range(k):
if sum(grid[r + i][c:c + k]) != expected:
return False
if sum(grid[r + j][c + i] for j in range(k)) != expected:
return False
if sum(grid[r + i][c + i] for i in range(k)) != expected:
return False
if sum(grid[r + i][c + k - i - 1] for i in range(k)) != expected:
return False
return Trueclass Solution {
public int largestMagicSquare(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int size = Math.min(m, n); size > 0; size--) {
for (int i = 0; i + size <= m; i++) {
for (int j = 0; j + size <= n; j++) {
if (isMagicSquare(grid, i, j, size)) {
return size;
}
}
}
}
return 1;
}
private boolean isMagicSquare(int[][] grid, int r, int c, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += grid[r][c + i];
for (int i = 0; i < k; i++) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < k; j++) {
rowSum += grid[r + i][c + j];
colSum += grid[r + j][c + i];
}
if (rowSum != sum || colSum != sum) return false;
}
int diag1 = 0, diag2 = 0;
for (int i = 0; i < k; i++) {
diag1 += grid[r + i][c + i];
diag2 += grid[r + i][c + k - i - 1];
}
return diag1 == sum && diag2 == sum;
}
}#include <vector>
using namespace std;
class Solution {
public:
int largestMagicSquare(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
for (int size = min(m, n); size > 0; --size) {
for (int i = 0; i + size <= m; ++i) {
for (int j = 0; j + size <= n; ++j) {
if (isMagicSquare(grid, i, j, size)) {
return size;
}
}
}
}
return 1;
}
private:
bool isMagicSquare(vector<vector<int>>& grid, int r, int c, int k) {
int sum = 0;
for (int i = 0; i < k; ++i) sum += grid[r][c + i];
for (int i = 0; i < k; ++i) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < k; ++j) {
rowSum += grid[r + i][c + j];
colSum += grid[r + j][c + i];
}
if (rowSum != sum || colSum != sum) return false;
}
int diag1 = 0, diag2 = 0;
for (int i = 0; i < k; ++i) {
diag1 += grid[r + i][c + i];
diag2 += grid[r + i][c + k - i - 1];
}
return diag1 == sum && diag2 == sum;
}
};function largestMagicSquare(grid) {
let m = grid.length, n = grid[0].length;
for (let size = Math.min(m, n); size > 0; size--) {
for (let i = 0; i + size <= m; i++) {
for (let j = 0; j + size <= n; j++) {
if (isMagicSquare(grid, i, j, size)) {
return size;
}
}
}
}
return 1;
}
function isMagicSquare(grid, r, c, k) {
let sum = 0;
for (let i = 0; i < k; i++) sum += grid[r][c + i];
for (let i = 0; i < k; i++) {
let rowSum = 0, colSum = 0;
for (let j = 0; j < k; j++) {
rowSum += grid[r + i][c + j];
colSum += grid[r + j][c + i];
}
if (rowSum !== sum || colSum !== sum) return false;
}
let diag1 = 0, diag2 = 0;
for (let i = 0; i < k; i++) {
diag1 += grid[r + i][c + i];
diag2 += grid[r + i][c + k - i - 1];
}
return diag1 === sum && diag2 === sum;
}#include <stdio.h>;
#include <stdbool.h>;
bool isMagicSquare(int **grid, int m, int n, int r, int c, int k);
int largestMagicSquare(int **grid, int m, int n) {
for (int size = (m < n ? m : n); size > 0; size--) {
for (int i = 0; i <= m - size; i++) {
for (int j = 0; j <= n - size; j++) {
if (isMagicSquare(grid, m, n, i, j, size)) {
return size;
}
}
}
}
return 1;
}
bool isMagicSquare(int **grid, int m, int n, int r, int c, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += grid[r][c + i];
for (int i = 0; i < k; i++) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < k; j++) {
rowSum += grid[r + i][c + j];
colSum += grid[r + j][c + i];
}
if (rowSum != sum || colSum != sum) return false;
}
int diag1 = 0, diag2 = 0;
for (int i = 0; i < k; i++) {
diag1 += grid[r + i][c + i];
diag2 += grid[r + i][c + k - i - 1];
}
return diag1 == sum && diag2 == sum;
}public class Solution {
public int LargestMagicSquare(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
for (int size = Math.Min(m, n); size > 0; size--) {
for (int i = 0; i + size <= m; i++) {
for (int j = 0; j + size <= n; j++) {
if (IsMagicSquare(grid, i, j, size)) {
return size;
}
}
}
}
return 1;
}
private bool IsMagicSquare(int[][] grid, int r, int c, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += grid[r][c + i];
for (int i = 0; i < k; i++) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < k; j++) {
rowSum += grid[r + i][c + j];
colSum += grid[r + j][c + i];
}
if (rowSum != sum || colSum != sum) return false;
}
int diag1 = 0, diag2 = 0;
for (int i = 0; i < k; i++) {
diag1 += grid[r + i][c + i];
diag2 += grid[r + i][c + k - i - 1];
}
return diag1 == sum && diag2 == sum;
}
}The Python solution also explores sub-grids row by row and column by column for potential square sizes. It performs sum checks on the rows, columns, and diagonals for each square to determine if it qualifies as a magic square.
Time Complexity: O(m * n * min(m, n)^2) where we check nested squares.
Space Complexity: O(1).
Approach 2: Optimized with Prefix Sums for Sums Calculation
This solution improves upon the naive magic square identification strategy by using prefix sums to rapidly calculate the sums of rows, columns, and diagonals. Pre-calculating this information allows for quicker checks when verifying potential squares. This reduces the time complexity of individual square verification and is particularly more efficient for larger grid sizes.
def largestMagicSquare(grid):
def calc_prefix_sums(grid):
# Calculates row-wise and column-wise prefix sums that aid in efficient sum calculation
# Implementation skipped.
pass
# Full Python implementation for this optimized method is omitted for brevity// Java can utilize arrays to store prefix sums, enabling rapid calculations. The main fostering of optimization is through controlled sub-grid sum verification leveraging these prefix sums.// C++ implementation involves similar precomputations as done in other languages given constraints provided.// JavaScript implementation commences with creating prefix sums arrays to reduce steps necessary for sum calculation./* Code for an optimized solution using prefix sums in C is omitted for brevity. Consider the prefix sums being generated for each row and column before calculating. */// Similarly structured to Python implementation, express precomputations for prefix sums to verify fast grid conditions for magic squares.By precomputing sums, achieved through prefix arrays, the validation of each possible k x k grid is reduced from linear operations per row and column to near constant time, thus In quick calculations of subgrid properties for magic square determination.
Time Complexity: O(m * n * min(m, n)) leveraging prefix sums.
Space Complexity: O(m * n).
Approach 3: Prefix Sum + Enumeration
We define rowsum[i][j] as the sum of elements in the i-th row up to the j-th column of the matrix, and colsum[i][j] as the sum of elements in the j-th column up to the i-th row. Thus, for any submatrix from (x_1, y_1) to (x_2, y_2), the sum of its i-th row can be expressed as rowsum[i+1][y_2+1] - rowsum[i+1][y_1], and the sum of its j-th column can be expressed as colsum[x_2+1][j+1] - colsum[x_1][j+1].
We enumerate all possible submatrices and check if they are magic squares. For each submatrix, we calculate the sum of each row, each column, and both diagonals to determine if they are all equal.
The time complexity is O(m times n times min(m, n)^2), and the space complexity is O(m times n).
function largestMagicSquare(grid: number[][]): number {
const [m, n] = [grid.length, grid[0].length];
const rowsum: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
const colsum: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1];
colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1];
}
}
const check = (x1: number, y1: number, x2: number, y2: number): boolean => {
const val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1];
for (let i = x1 + 1; i <= x2; ++i) {
if (rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] !== val) {
return false;
}
}
for (let j = y1; j <= y2; ++j) {
if (colsum[x2 + 1][j + 1] - colsum[x1][j + 1] !== val) {
return false;
}
}
let s = 0;
for (let i = x1, j = y1; i <= x2; ++i, ++j) {
s += grid[i][j];
}
if (s !== val) {
return false;
}
s = 0;
for (let i = x1, j = y2; i <= x2; ++i, --j) {
s += grid[i][j];
}
if (s !== val) {
return false;
}
return true;
};
for (let k = Math.min(m, n); k > 1; --k) {
for (let i = 0; i + k - 1 < m; ++i) {
for (let j = 0; j + k - 1 < n; ++j) {
const i2 = i + k - 1,
j2 = j + k - 1;
if (check(i, j, i2, j2)) {
return k;
}
}
}
}
return 1;
}func largestMagicSquare(grid [][]int) int {
m, n := len(grid), len(grid[0])
rowsum := make([][]int, m+1)
colsum := make([][]int, m+1)
for i := 0; i <= m; i++ {
rowsum[i] = make([]int, n+1)
colsum[i] = make([]int, n+1)
}
for i := 1; i < m+1; i++ {
for j := 1; j < n+1; j++ {
rowsum[i][j] = rowsum[i][j-1] + grid[i-1][j-1]
colsum[i][j] = colsum[i-1][j] + grid[i-1][j-1]
}
}
for k := min(m, n); k > 1; k-- {
for i := 0; i+k-1 < m; i++ {
for j := 0; j+k-1 < n; j++ {
i2, j2 := i+k-1, j+k-1
if check(grid, rowsum, colsum, i, j, i2, j2) {
return k
}
}
}
}
return 1
}
func check(grid, rowsum, colsum [][]int, x1, y1, x2, y2 int) bool {
val := rowsum[x1+1][y2+1] - rowsum[x1+1][y1]
for i := x1 + 1; i < x2+1; i++ {
if rowsum[i+1][y2+1]-rowsum[i+1][y1] != val {
return false
}
}
for j := y1; j < y2+1; j++ {
if colsum[x2+1][j+1]-colsum[x1][j+1] != val {
return false
}
}
s := 0
for i, j := x1, y1; i <= x2; i, j = i+1, j+1 {
s += grid[i][j]
}
if s != val {
return false
}
s = 0
for i, j := x1, y2; i <= x2; i, j = i+1, j-1 {
s += grid[i][j]
}
if s != val {
return false
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Prefix Sums | Time Complexity: O(m * n * min(m, n)^2) where we check nested squares. |
| Optimized with Prefix Sums for Sums Calculation | Time Complexity: O(m * n * min(m, n)) leveraging prefix sums. |
| Prefix Sum + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Prefix Sums | O(m * n * k^2) | O(m * n) | Good for understanding the validation process of magic squares and practicing prefix sum queries |
| Optimized Prefix Sum Verification | O(m * n * min(m,n)) | O(m * n) | Preferred solution for interviews and production due to faster validation and early termination |
Frequently asked questions
Is Largest Magic Square easy or hard?
Largest Magic Square is rated Medium difficulty on LeetCode. The challenge comes from efficiently validating multiple subgrids and using prefix sums to avoid recomputing sums repeatedly.
Largest Magic Square Python/Java solution
Python and Java solutions typically precompute row and column prefix sums, then iterate over square sizes while verifying row, column, and diagonal sums. The logic is identical across languages, differing mainly in syntax and array handling.
How to solve Largest Magic Square in O(n)?
A strictly O(n) solution is not possible because multiple square subgrids must be examined. The best practical complexity is O(m * n * min(m,n)) using prefix sums to check row and column sums quickly while iterating through candidate square sizes.
What is the best approach for Largest Magic Square?
The most efficient approach uses row and column prefix sums to compute segment sums in O(1). Iterate over possible square sizes and verify row, column, and diagonal sums using the prefix arrays. This reduces repeated summation and results in roughly O(m * n * min(m,n)) time complexity.
Is Largest Magic Square asked at Google/Amazon/Meta?
Grid validation and prefix sum problems similar to Largest Magic Square appear in interviews at companies like Amazon and Google. These companies often test matrix traversal, prefix sum optimization, and subgrid validation techniques.
What data structure is used in Largest Magic Square?
The main data structures are 2D arrays and prefix sum arrays. Row and column prefix sums allow constant-time range sum queries, which makes it efficient to verify row and column sums for each candidate square.
What is the time complexity of Largest Magic Square?
The optimized solution runs in O(m * n * min(m,n)) time because each possible square is validated using constant-time prefix sum queries and linear checks across rows or columns. Space complexity is O(m * n) for storing row and column prefix sums.