Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A magic square has the same sum in every row, every column, and both main diagonals. Prefix sums in those four directions make each line sum a constant-time query. Trying larger squares first lets the first valid candidate determine the answer.

Approach

Precompute horizontal, vertical, downward-right diagonal, and downward-left diagonal prefix sums. Enumerate side lengths from min(rows, columns) down to one and every fitting top-left corner. Compare the two diagonals first, then each row and column against that common sum, rejecting on the first mismatch. Return the side length of the first passing square. Unlike a 1-through-9 magic-square problem, this task does not require distinct values; a single cell is always valid.

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        prow = [[0 for _ in range(m)] for _ in range(n)]
        pcol = [[0 for _ in range(m)] for _ in range(n)]
        pd1 = [[0 for _ in range(m)] for _ in range(n)]
        pd2 = [[0 for _ in range(m)] for _ in range(n)]

        for i in range(n):
            for j in range(m):
                curr = grid[i][j]
                prow[i][j] = curr + (prow[i][j - 1] if j > 0 else 0)
                pcol[i][j] = curr + (pcol[i - 1][j] if i > 0 else 0)
                pd1[i][j] = curr + (pd1[i - 1][j - 1] if i > 0 and j > 0 else 0)
                pd2[i][j] = curr + (pd2[i - 1][j + 1] if i > 0 and j < m - 1 else 0)

        for k in range(min(n, m), 0, -1):
            for i in range(n):
                for j in range(m):
                    if i + k > n or j + k > m:
                        continue
                    d1 = pd1[i + k - 1][j + k - 1] - (pd1[i - 1][j - 1] if i > 0 and j > 0 else 0)
                    d2 = pd2[i + k - 1][j] - (pd2[i - 1][j + k] if i > 0 and j + k < m else 0)
                    if d1 != d2:
                        continue
                    valid = True
                    for row in range(i, i + k):
                        if prow[row][j + k - 1] - (prow[row][j - 1] if j > 0 else 0) != d1:
                            valid = False
                            break
                    if not valid:
                        continue
                    valid = True
                    for col in range(j, j + k):
                        if pcol[i + k - 1][col] - (pcol[i - 1][col] if i > 0 else 0) != d1:
                            valid = False
                            break
                    if valid:
                        return k

        return 1

Complexity analysis

Let r and c be the grid dimensions and d = min(r, c). Time: O(r * c * d^2) in the worst case while checking every candidate size and its rows/columns. Auxiliary space: O(r * c) for four prefix-sum matrices.