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] <= 106This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
The Korean king's magic square: a brilliant algorithm in a k-drama (plus geomagic squares) • Mathologer • 133,385 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