Skip to main content
Talentd

Largest Magic Square - Solution & Explanation

MediumArrayMatrixPrefix Sum23 min readAsked at: Amazon, Google, Wayfair
Practice this problem

Problem Statement

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.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= 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.

This code consists of two main functions. The isMagicSquare function checks if a given sub-grid defined by its top-left corner (r, c) and size k is a magic square by checking row, column, and diagonal sums. The main function, largestMagicSquare, iterates over all possible sizes of squares, trying to find the largest magic square starting from any grid cell.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * min(m, n)^2), as for each potential square we check all rows, columns, and diagonals at different sizes.
Space Complexity: O(1), no additional space is used other than a few variables to store sums.

Try this approach in the editor →

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.

By precomputing prefix sums for rows and columns, the implementation of this solution reduces the number of operations necessary to verify sum conditions on the subgrids. The main complexity reduction is in the time taken to assess given squares.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * min(m, n)) due to efficient row/column sum computation via prefix sums.
Space Complexity: O(m * n) for storing the prefix sums.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force with Prefix Sums

Time Complexity: O(m * n * min(m, n)^2), as for each potential square we check all rows, columns, and diagonals at different sizes.
Space Complexity: O(1), no additional space is used other than a few variables to store sums.

Optimized with Prefix Sums for Sums Calculation

Time Complexity: O(m * n * min(m, n)) due to efficient row/column sum computation via prefix sums.
Space Complexity: O(m * n) for storing the prefix sums.

Prefix Sum + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Prefix SumsO(m * n * k^2)O(m * n)Good for understanding the validation process of magic squares and practicing prefix sum queries
Optimized Prefix Sum VerificationO(m * n * min(m,n))O(m * n)Preferred solution for interviews and production due to faster validation and early termination

Video Solution

Leetcode 1895. Largest Magic Square • Fraz • 6,374 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Largest Magic Square with our built-in code editor and test cases.

Practice on FleetCode
Previous

Magic Squares In Grid