Problem Statement in English

You’re given an m x n integer grid grid. A magic square is a k x k square subgrid (where k >= 2) where the sums of all rows, the sums of all columns, and the sums of both diagonals are all equal.

Return the size k of the largest magic square that can be found in grid. If no magic square exists, return 1.

Approach

You can use a brute-force approach to check all possible k x k subgrids in the given grid.

For each subgrid, you need to verify if it satisfies the conditions of being a magic square by checking the sums of its rows, columns, and diagonals.

Solution in Python


class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 1

        def isValid(i, j, k):
            s = None
            for x in range(i, i + k):
                row = sum(grid[x][j:j + k])
                if s is None: s = row
                elif s != row: return False

            for y in range(j, j + k):
                if sum(grid[x][y] for x in range(i, i + k)) != s:
                    return False

            if sum(grid[i + d][j + d] for d in range(k)) != s:
                return False

            if sum(grid[i + d][j + k - 1 - d] for d in range(k)) != s:
                return False

            return True

        for k in range(2, min(m, n) + 1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if isValid(i, j, k):
                        res = k
        return res

Complexity

  • Time: O(m×n×min⁡(m,n)2)O(m \times n \times \min(m, n)^2)

  • Space: O(1)O(1)
    Since we are using only constant extra space.

Mistakes I Made

I didn’t think that the naive approach would work within the constraints. But it does.

And we are done.