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] <= 106Problem 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.
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.
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.
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.
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.
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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. |
| 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. |
| Prefix Sum + Enumeration | — |
| 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 |
Largest Magic Square | Simplified Explanation | Leetcode 1895 | codestorywithMIK • codestorywithMIK • 9,328 views views
Watch 9 more video solutions →Practice Largest Magic Square with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor