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.

Description Hints 1 Solution Video 9:06

1895. Largest Magic Square

Medium75.3% acceptance3 companies

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] <= 10⁶

Asked at 3 companies

Wayfair

Google Amazon

Topics

Hints open one at a time

Hint 1

Check all squares in the matrix and find the largest one.

9:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution