{x}
blog image

Largest Magic Square

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] <= 106

Solution Explanation

This problem asks to find the largest magic square within a given grid. A magic square is a square grid where the sum of each row, column, and both diagonals are equal. The solution uses a prefix sum approach to efficiently check for magic squares of various sizes.

Approach:

  1. Prefix Sum: The solution first computes the prefix sums for rows and columns. rowsum[i][j] stores the sum of elements in row i from column 1 to j, and similarly for colsum. This allows for O(1) calculation of the sum of any sub-array.

  2. Iterative Check: The code iterates through potential magic square sizes, starting from the maximum possible size (min(m, n)) down to 1. For each size k, it iterates through all possible k x k subgrids.

  3. check() Function: The core logic resides in the check() function. This function verifies if a given k x k subgrid is a magic square. It does this by:

    • Calculating the sum of the first row.
    • Checking if all other rows have the same sum.
    • Checking if all columns have the same sum.
    • Checking if both diagonals have the same sum.

  4. Return Value: If a magic square of size k is found, the function immediately returns k. If no magic square is found for any size, it returns 1 (as a 1x1 grid is always a magic square).

Time Complexity Analysis:

  • Prefix sum calculation takes O(m*n) time.
  • The nested loops iterate through all possible subgrid sizes and positions. The number of k x k subgrids is roughly O((m-k+1)(n-k+1)). Since k ranges from 1 to min(m,n), the total number of iterations is approximately O(m*n).
  • The check() function takes O(k) time.

Therefore, the overall time complexity is dominated by the nested loops and is O(mnmin(m,n)). This could be approximated as O(m²n) if m and n are of similar magnitude.

Space Complexity Analysis:

  • The prefix sum matrices rowsum and colsum require O(m*n) space.
  • Other variables use constant space.

Therefore, the space complexity is O(m*n).

Code Explanation (Python):

The Python code follows the approach described above. The rowsum and colsum are initialized, and the check() function verifies the magic square property. The main loop efficiently searches for magic squares of decreasing sizes.

Code Explanation (Other Languages):

The Java, C++, Go, and TypeScript codes implement the same algorithm with minor syntactic differences. The core logic remains consistent across all languages. The prefix sum arrays are created and used to efficiently calculate row and column sums. The check function performs the validation of the magic square property. The main loop iterates through possible square sizes and checks subgrids within the grid for the magic square property.