Skip to content

1895. Largest Magic Square

Difficulty Topics

Description

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

largest-magic-square.py
class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        self.res = 1

        rowPrefix = [[i for i in row] for row in grid]
        colPrefix = [[i for i in row] for row in grid]
        dlPrefix = [[i for i in row] for row in grid]
        drPrefix = [[i for i in row] for row in grid]

        # row
        for i in range(rows):
            for j in range(cols - 1):
                rowPrefix[i][j + 1] += rowPrefix[i][j]

        # cols
        for i in range(rows - 1):
            for j in range(cols):
                colPrefix[i + 1][j] += colPrefix[i][j]

        # diag left
        for i in range(rows - 1):
            for j in range(cols - 1):
                dlPrefix[i + 1][j + 1] += dlPrefix[i][j]

        # diag right
        for i in range(rows - 1):
            for j in range(cols - 1, 0, -1):
                drPrefix[i + 1][j - 1] += drPrefix[i][j]

        def dfs(x, y, size):

            if x + size < rows and y + size < cols:
                rowSum = [rowPrefix[i][y + size] - (0 if y == 0 else rowPrefix[i][y - 1]) for i in range(x, x + size + 1)]
                colSum = [colPrefix[x + size][j] - (0 if x == 0 else colPrefix[x - 1][j]) for j in range(y, y + size + 1)]
                diagLeft = dlPrefix[x + size][y + size] - (0 if x == 0 or y == 0 else dlPrefix[x - 1][y - 1])
                diagRight = drPrefix[x + size][y] - (0 if x - 1 < 0 or y + size + 1 >= cols else drPrefix[x - 1][y + size + 1])

                if (all(r == rowSum[0] for r in rowSum) and all(c == colSum[0] for c in colSum) and rowSum[0] == colSum[0] == diagLeft == diagRight):
                    self.res = max(self.res, size + 1)

                dfs(x, y, size + 1)

        for i in range(rows):
            for j in range(cols):
                dfs(i, j, 1)

        return self.res