1895. Largest Magic Square (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def largestMagicSquare(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        prefix_row = [[0] * (n + 1) for _ in range(m)]
        prefix_col = [[0] * (n) for _ in range(m + 1)]
        for i in range(m):
            for j in range(n):
                prefix_row[i][j + 1] += prefix_row[i][j] + grid[i][j]
                prefix_col[i + 1][j] += prefix_col[i][j] + grid[i][j]
        for x in range(min(m, n), 1, -1):
            for i in range(m - x + 1):
                for j in range(n - x + 1):
                    diag1 = diag2 = 0
                    s = prefix_row[i][j + x] - prefix_row[i][j]
                    for y in range(x):
                        if s != prefix_row[i + y][j + x] - prefix_row[i + y][j] or s != prefix_col[i + x][j + y] - prefix_col[i][j + y]:
                            break
                        diag1 += grid[i + y][j + y]
                        diag2 += grid[i + y][j + x - y - 1]
                    if s == diag1 == diag2:
                        return x
        return 1