#1895

Medium

LeetCode Problem Workspace

Largest Magic Square

Find the side length of the largest magic square in a matrix where row, column, and diagonal sums are equal.

Problem Statement

A k x k magic square is a square subgrid filled with integers such that the sum of every row, every column, and both main diagonals are equal. Single-cell squares are trivially magic squares.

Given an m x n integer grid, return the largest integer k representing the side length of a magic square contained in the grid. For example, in grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]], the largest magic square has size 3.

Examples

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

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

Example details omitted.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
1 <= grid[i][j] <= 106

Solution Approach

Use Prefix Sums for Rows and Columns

Precompute prefix sums for rows and columns to quickly calculate sums of any subgrid. This reduces redundant summations and allows O(1) retrieval of row and column totals for candidate squares, directly targeting the failure mode of recomputing sums for each square.

Iterate Over All Square Sizes

Check every possible k x k square starting from each cell. For each square, verify if all row sums, column sums, and both diagonal sums are equal. This exhaustive search ensures no potential magic square is missed, leveraging the Array plus Matrix pattern for systematic validation.

Track Maximum Valid Size

Maintain a variable for the largest valid k found. Update only when a square meets the magic square condition. This approach prevents overcounting smaller squares inside larger valid squares, aligning with the common interview signal of optimizing for largest valid subgrid.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on iterating all possible square sizes and validating sums: roughly O(min(m,n)^3) with prefix sums. Space complexity is O(m*n) for prefix sum storage.

What Interviewers Usually Probe

Focus on using prefix sums to avoid recalculating sums for each square.
Expect you to consider all candidate squares and check diagonal sums carefully.
Watch for off-by-one errors when indexing subgrids in the matrix.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check both diagonals, leading to false positives.
Recomputing row and column sums repeatedly without prefix sums.
Misindexing when iterating subgrids or when calculating square boundaries.

Follow-up variants

Find the total number of magic squares of all sizes in a grid instead of the largest.
Return the top-left coordinate of the largest magic square along with its size.
Allow only distinct integers inside magic squares, increasing validation complexity.

FAQ

What is the Largest Magic Square problem about?

It asks for the side length of the largest square subgrid where all rows, columns, and diagonals sum to the same value.

Why are prefix sums recommended for this problem?

Prefix sums let you compute row and column sums quickly, avoiding repeated summation in nested loops.

Can a magic square contain repeated integers?

Yes, the problem allows repeated integers; only the sums need to match, not the uniqueness of elements.

How do you verify diagonals efficiently?

Compute diagonals separately using the starting coordinate and iterating k steps; prefix sums help only for rows and columns.

What is the main pattern for solving this problem?

The Array plus Matrix pattern: iterate all subgrids while using array prefix sums for quick row and column sum checks.

terminal

Solution

Solution 1: Prefix Sum + Enumeration

We define $\text{rowsum}[i][j]$ as the sum of elements in the $i$-th row up to the $j$-th column of the matrix, and $\text{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 $\text{rowsum}[i+1][y_2+1] - \text{rowsum}[i+1][y_1]$, and the sum of its $j$-th column can be expressed as $\text{colsum}[x_2+1][j+1] - \text{colsum}[x_1][j+1]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        rowsum = [[0] * (n + 1) for _ in range(m + 1)]
        colsum = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1]
                colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1]

        def check(x1, y1, x2, y2):
            val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1]
            for i in range(x1 + 1, x2 + 1):
                if rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val:
                    return False
            for j in range(y1, y2 + 1):
                if colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val:
                    return False
            s, i, j = 0, x1, y1
            while i <= x2:
                s += grid[i][j]
                i += 1
                j += 1
            if s != val:
                return False
            s, i, j = 0, x1, y2
            while i <= x2:
                s += grid[i][j]
                i += 1
                j -= 1
            if s != val:
                return False
            return True

        for k in range(min(m, n), 1, -1):
            i = 0
            while i + k - 1 < m:
                j = 0
                while j + k - 1 < n:
                    i2, j2 = i + k - 1, j + k - 1
                    if check(i, j, i2, j2):
                        return k
                    j += 1
                i += 1
        return 1

Continue Practicing

#1878 get biggest three rhombus sums in a grid #2017 grid game #1738 find kth largest xor coordinate value