We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Magic Square

Number: 1311

Difficulty: Medium

Paid? No

Companies: Wayfair

Problem Description

Given an m x n grid filled with integers, determine the side length k of the largest k x k subgrid that forms a magic square. A magic square is one where every row sum, every column sum, and both diagonal sums are equal. Note that the integers do not have to be distinct, and every 1 x 1 grid is trivially a magic square.

Key Insights

  • A magic square requires that all k row sums, k column sums, and the two diagonal sums are equal.
  • Brute force: iterate over every possible k x k subgrid in the matrix and check the sums.
  • Use the first row sum (or any row) as the reference sum and compare sums of the remaining rows, columns, and two diagonals against it.
  • Given the constraints (grid dimensions up to 50), a solution that checks every possible subgrid is acceptable.

Space and Time Complexity

Time Complexity: O(m * n * min(m, n)), where m and n are the dimensions of the grid. For each potential subgrid O(m*n), we check up to O(min(m,n)) elements. Space Complexity: O(1) extra space (ignoring the input storage).

Solution

The solution uses a brute force approach to examine every possible subgrid in the given grid starting from the largest possible size and decreasing to 1. For each subgrid defined by its top-left corner and size k, it computes the sum of the first row and verifies that all other rows, all columns, and both the main and secondary diagonals sum to the same value. If a valid magic square is found, the size k is returned immediately. The use of simple loops is sufficient given the constrained problem size.

Code Solutions

# Python solution for Largest Magic Square
class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        
        # Helper function to check if the subgrid starting at (row, col)
        # of size k forms a magic square.
        def isMagic(row, col, k):
            # Reference sum of the first row of the subgrid.
            target = sum(grid[row][col:col+k])
            
            # Check each row sum.
            for i in range(row, row+k):
                if sum(grid[i][col:col+k]) != target:
                    return False
                
            # Check each column sum.
            for j in range(col, col+k):
                col_sum = 0
                for i in range(row, row+k):
                    col_sum += grid[i][j]
                if col_sum != target:
                    return False
            
            # Check the main diagonal.
            diag_sum1 = 0
            for i in range(k):
                diag_sum1 += grid[row+i][col+i]
            if diag_sum1 != target:
                return False
            
            # Check the secondary diagonal.
            diag_sum2 = 0
            for i in range(k):
                diag_sum2 += grid[row+i][col+k-1-i]
            if diag_sum2 != target:
                return False
            
            return True
        
        # Try squares from the largest possible size to 1.
        for k in range(min(m, n), 0, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if isMagic(i, j, k):
                        return k
        return 1  # This line is theoretically unreachable since 1x1 is always magic.
← Back to All Questions