Largest Magic Square

Med

#1729Time: O(m * n * min(m, n)^3). Let `L = min(m, n)`. There are three nested loops for `k`, `r`, and `c`, giving `O(L * m * n)` iterations. Inside, the `isMagic` check takes `O(k^2)` time as it computes `~2k` sums, each taking `O(k)` time. This results in an overall complexity of roughly `O(m * n * L^3)`, or `O(N^5)` if `m` and `n` are similar.Space: O(1) extra space. The algorithm only uses a few variables to store sums during the check, not dependent on the input size.1 company

Patterns

Prefix Sum

Data structures

Array Matrix

Companies

Wayfair

Prompt

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⁶

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves a straightforward, exhaustive search. It checks every possible square subgrid within the given m x n grid to see if it qualifies as a magic square. To find the largest one, we start by checking for the largest possible square size and progressively decrease the size until a magic square is found.

Algorithm

Iterate through all possible side lengths k for a square, starting from the maximum possible size, min(m, n), down to 2.
For each size k, iterate through all possible top-left corners (r, c) of a k x k subgrid.
For each subgrid, call a helper function isMagic(r, c, k) to verify if it's a magic square.
The isMagic function calculates the sum of all rows, all columns, and both diagonals of the subgrid. It first computes a target sum (e.g., from the main diagonal) and then compares all other 2k+1 sums to this target. Each sum calculation requires iterating through k elements.
If all sums are equal, a magic square of size k is found. Since we are iterating k downwards, this is the largest possible magic square, and we can immediately return k.
If the loops complete without finding any magic square of size 2 or greater, return 1.

Walkthrough

The algorithm iterates through all possible side lengths k for a square, starting from min(m, n) down to 2. A size of 1 is the base case, as any 1x1 grid is a magic square. For each size k, we check every possible k x k subgrid. A subgrid is defined by its top-left corner (r, c). For each subgrid, we verify the magic square property: all row sums, column sums, and the two diagonal sums must be equal. This is done by first calculating a target_sum (e.g., the sum of the main diagonal) and then calculating and comparing all other 2k+1 sums against it. Each sum calculation involves a loop of k elements. If a magic square of size k is found, we can immediately return k because we are searching in decreasing order of size. If no magic square larger than 1x1 is found, the function returns 1.

1class Solution {2    public int largestMagicSquare(int[][] grid) {3        int m = grid.length;4        int n = grid[0].length;5        for (int k = Math.min(m, n); k >= 2; k--) {6            for (int r = 0; r <= m - k; r++) {7                for (int c = 0; c <= n - k; c++) {8                    if (isMagic(grid, r, c, k)) {9                        return k;10                    }11                }12            }13        }14        return 1;15    }16 17    private boolean isMagic(int[][] grid, int r, int c, int k) {18        long diag1Sum = 0;19        for (int i = 0; i < k; i++) {20            diag1Sum += grid[r + i][c + i];21        }22 23        long diag2Sum = 0;24        for (int i = 0; i < k; i++) {25            diag2Sum += grid[r + i][c + k - 1 - i];26        }27        if (diag1Sum != diag2Sum) {28            return false;29        }30 31        for (int i = 0; i < k; i++) {32            long rowSum = 0;33            for (int j = 0; j < k; j++) {34                rowSum += grid[r + i][c + j];35            }36            if (rowSum != diag1Sum) {37                return false;38            }39        }40 41        for (int j = 0; j < k; j++) {42            long colSum = 0;43            for (int i = 0; i < k; i++) {44                colSum += grid[r + i][c + j];45            }46            if (colSum != diag1Sum) {47                return false;48            }49        }50 51        return true;52    }53}

Complexity

Time

O(m * n * min(m, n)^3). Let `L = min(m, n)`. There are three nested loops for `k`, `r`, and `c`, giving `O(L * m * n)` iterations. Inside, the `isMagic` check takes `O(k^2)` time as it computes `~2k` sums, each taking `O(k)` time. This results in an overall complexity of roughly `O(m * n * L^3)`, or `O(N^5)` if `m` and `n` are similar.

Space

O(1) extra space. The algorithm only uses a few variables to store sums during the check, not dependent on the input size.

Trade-offs

Pros

Simple to understand and implement.
Requires no extra space, operating in-place on the input grid.

Cons

Highly inefficient due to redundant calculations of sums for overlapping subgrids.
Likely to result in a 'Time Limit Exceeded' error for larger grid sizes within the given constraints.

This approach significantly optimizes the brute-force method by using a dynamic programming technique known as prefix sums (or integral images). By pre-calculating the sums of all row and column prefixes, we can find the sum of any row or column segment in constant O(1) time. This drastically speeds up the process of checking if a subgrid is a magic square.

Algorithm

First, pre-calculate prefix sums for all rows and columns of the grid. Create two auxiliary matrices: rowPrefixSum and colPrefixSum.
rowPrefixSum[i][j] will store the sum of elements in grid[i] from column 0 to j-1.
colPrefixSum[i][j] will store the sum of elements in grid's column j from row 0 to i-1.
This preprocessing step takes O(m * n) time.
Then, iterate k from min(m, n) down to 2.
For each k, iterate through all top-left corners (r, c).
For each subgrid, check if it's a magic square:
- Calculate the main and anti-diagonal sums in O(k) time.
- Use the pre-calculated prefix sum matrices to find each of the k row sums and k column sums in O(1) time per sum.
- Compare all sums. If they are equal, return k.
If the loops finish, return 1.

Walkthrough

The main bottleneck in the brute-force approach is the repeated calculation of row and column sums. This can be optimized by pre-computation. We create two matrices, rowPrefixSum and colPrefixSum, to store these cumulative sums. rowPrefixSum[i][c+1] holds the sum grid[i][0] + ... + grid[i][c], and colPrefixSum[r+1][j] holds grid[0][j] + ... + grid[r][j]. These can be built in O(m*n) time.

With these structures, the sum of a row segment grid[r][c...c+k-1] is simply rowPrefixSum[r][c+k] - rowPrefixSum[r][c], an O(1) operation. The same applies to column sums.

The overall structure of iterating from the largest possible size k downwards remains. However, the check for each subgrid becomes much faster. While diagonal sums still take O(k) to compute, checking all k row sums and k column sums now takes a total of O(k) time instead of O(k^2). This reduces the complexity of checking a single subgrid from O(k^2) to O(k), leading to a substantial overall performance gain.

1class Solution {2    public int largestMagicSquare(int[][] grid) {3        int m = grid.length;4        int n = grid[0].length;5 6        long[][] rowPrefixSum = new long[m][n + 1];7        for (int i = 0; i < m; i++) {8            for (int j = 0; j < n; j++) {9                rowPrefixSum[i][j + 1] = rowPrefixSum[i][j] + grid[i][j];10            }11        }12 13        long[][] colPrefixSum = new long[m + 1][n];14        for (int j = 0; j < n; j++) {15            for (int i = 0; i < m; i++) {16                colPrefixSum[i + 1][j] = colPrefixSum[i][j] + grid[i][j];17            }18        }19 20        for (int k = Math.min(m, n); k >= 2; k--) {21            for (int r = 0; r <= m - k; r++) {22                for (int c = 0; c <= n - k; c++) {23                    if (isMagic(grid, r, c, k, rowPrefixSum, colPrefixSum)) {24                        return k;25                    }26                }27            }28        }29        return 1;30    }31 32    private boolean isMagic(int[][] grid, int r, int c, int k, long[][] rowPrefixSum, long[][] colPrefixSum) {33        long diag1Sum = 0;34        for (int i = 0; i < k; i++) {35            diag1Sum += grid[r + i][c + i];36        }37 38        long diag2Sum = 0;39        for (int i = 0; i < k; i++) {40            diag2Sum += grid[r + i][c + k - 1 - i];41        }42        if (diag1Sum != diag2Sum) {43            return false;44        }45 46        for (int i = 0; i < k; i++) {47            long rowSum = rowPrefixSum[r + i][c + k] - rowPrefixSum[r + i][c];48            if (rowSum != diag1Sum) {49                return false;50            }51        }52 53        for (int j = 0; j < k; j++) {54            long colSum = colPrefixSum[r + k][c + j] - colPrefixSum[r][c + j];55            if (colSum != diag1Sum) {56                return false;57            }58        }59 60        return true;61    }62}

Complexity

Time

O(m * n * min(m, n)^2). Preprocessing takes `O(m * n)`. The main loops iterate `O(m * n * L)` times, where `L = min(m, n)`. The check for a `k x k` subgrid takes `O(k)` time. The total time is roughly `O(m * n * L^2)`, or `O(N^4)` if `m` and `n` are similar.

Space

O(m * n) to store the two prefix sum matrices. Each matrix has a size comparable to the input grid.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Passes within typical time limits for the given constraints.

Cons

Requires additional space proportional to the size of the grid to store the prefix sum matrices.

Solutions

Solution

1class Solution { private int [][] rowsum ; private int [][] colsum ; public int largestMagicSquare ( int [][] grid ) { int m = grid . length , n = grid [ 0 ]. length ; rowsum = new int [ m + 1 ][ n + 1 ]; colsum = new int [ m + 1 ][ n + 1 ]; for ( int i = 1 ; i <= m ; ++ i ) { for ( int 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 ]; } } for ( int k = Math . min ( m , n ); k > 1 ; -- k ) { for ( int i = 0 ; i + k - 1 < m ; ++ i ) { for ( int j = 0 ; j + k - 1 < n ; ++ j ) { int i2 = i + k - 1 , j2 = j + k - 1 ; if ( check ( grid , i , j , i2 , j2 )) { return k ; } } } } return 1 ; } private boolean check ( int [][] grid , int x1 , int y1 , int x2 , int y2 ) { int val = rowsum [ x1 + 1 ][ y2 + 1 ] - rowsum [ x1 + 1 ][ y1 ]; for ( int i = x1 + 1 ; i <= x2 ; ++ i ) { if ( rowsum [ i + 1 ][ y2 + 1 ] - rowsum [ i + 1 ][ y1 ] != val ) { return false ; } } for ( int j = y1 ; j <= y2 ; ++ j ) { if ( colsum [ x2 + 1 ][ j + 1 ] - colsum [ x1 ][ j + 1 ] != val ) { return false ; } } int s = 0 ; for ( int i = x1 , j = y1 ; i <= x2 ; ++ i , ++ j ) { s += grid [ i ][ j ]; } if ( s != val ) { return false ; } s = 0 ; for ( int i = x1 , j = y2 ; i <= x2 ; ++ i , -- j ) { s += grid [ i ][ j ]; } if ( s != val ) { return false ; } return true ; } }

1class Solution {2public:3  int largestMagicSquare(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid.size();5    vector<vector<int>> rowsum(m + 1, vector<int>(n + 1));6    vector<vector<int>> colsum(m + 1, vector<int>(n + 1));7    for (int i = 1; i <= m; ++i) {8      for (int j = 1; j <= n; ++j) {9        rowsum[i][j] = rowsum[i][j - 1] + grid[i - 1][j - 1];10        colsum[i][j] = colsum[i - 1][j] + grid[i - 1][j - 1];11      }12    }13    for (int k = min(m, n); k > 1; --k) {14      for (int i = 0; i + k - 1 < m; ++i) {15        for (int j = 0; j + k - 1 < n; ++j) {16          int i2 = i + k - 1, j2 = j + k - 1;17          if (check(grid, rowsum, colsum, i, j, i2, j2))18            return k;19        }20      }21    }22    return 1;23  }24  bool check(vector<vector<int>> &grid, vector<vector<int>> &rowsum,25             vector<vector<int>> &colsum, int x1, int y1, int x2, int y2) {26    int val = rowsum[x1 + 1][y2 + 1] - rowsum[x1 + 1][y1];27    for (int i = x1 + 1; i <= x2; ++i)28      if (rowsum[i + 1][y2 + 1] - rowsum[i + 1][y1] != val)29        return false;30    for (int j = y1; j <= y2; ++j)31      if (colsum[x2 + 1][j + 1] - colsum[x1][j + 1] != val)32        return false;33    int s = 0;34    for (int i = x1, j = y1; i <= x2; ++i, ++j)35      s += grid[i][j];36    if (s != val)37      return false;38    s = 0;39    for (int i = x1, j = y2; i <= x2; ++i, --j)40      s += grid[i][j];41    if (s != val)42      return false;43    return true;44  }45};

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem