Largest Magic Square: Prefix Sums on a Matrix

A magic square is a grid where every row, every column, and both diagonals all add up to the same number. They have fascinated mathematicians for thousands of years, and now they show up in coding interviews too. The twist in this problem is that you are not building a magic square from scratch. You are searching for the largest one hiding inside a bigger grid.

The problem

LeetCode 1895: Largest Magic Square. Given an m x n integer grid, return the size of the largest magic square that can be found within the grid. A magic square is a k x k subgrid where the sum of each row, each column, and both diagonals are all equal.

For example, consider this 3x4 grid. The highlighted 3x3 region is a magic square because every row, column, and diagonal sums to 15.

The brute force idea

The simplest approach: try every possible k x k subgrid, starting from the largest k and working down. For each candidate, compute all the row sums, column sums, and both diagonal sums. If they are all equal, you found your answer.

For each subgrid, computing a single row sum takes O(k), and there are 2k + 2 sums to check (k rows, k columns, 2 diagonals). That is O(k^2) per candidate. You have O(m * n) possible top-left corners and O(min(m, n)) possible values of k. The total time balloons quickly.

You can do better by precomputing prefix sums, which lets you compute any row or column sum in O(1) instead of O(k).

The optimized approach

Build two prefix sum arrays before you start checking:

1. Row prefix sums: rowPfx[r][c] stores the sum of row r from column 0 through column c - 1. The sum of columns c1 through c2 in row r is rowPfx[r][c2 + 1] - rowPfx[r][c1].

2. Column prefix sums: colPfx[r][c] stores the sum of column c from row 0 through row r - 1. The sum of rows r1 through r2 in column c is colPfx[r2 + 1][c] - colPfx[r1][c].

With these in place, checking a single row or column sum takes O(1). The diagonals still require an O(k) scan (since they are not axis-aligned), but the overall complexity improves significantly.

The algorithm then iterates from the largest possible k down to 1. For each k, it tries every valid top-left corner (r, c). It computes the target sum from the first row, then verifies all other rows, all columns, and both diagonals. The moment you find a valid magic square, return k.

Visual walkthrough

The code

def largestMagicSquare(grid):
    m, n = len(grid), len(grid[0])

    rowPfx = [[0] * (n + 1) for _ in range(m)]
    colPfx = [[0] * n for _ in range(m + 1)]

    for r in range(m):
        for c in range(n):
            rowPfx[r][c + 1] = rowPfx[r][c] + grid[r][c]
            colPfx[r + 1][c] = colPfx[r][c] + grid[r][c]

    def row_sum(r, c1, c2):
        return rowPfx[r][c2 + 1] - rowPfx[r][c1]

    def col_sum(c, r1, r2):
        return colPfx[r2 + 1][c] - colPfx[r1][c]

    def is_magic(r, c, k):
        target = row_sum(r, c, c + k - 1)

        for i in range(1, k):
            if row_sum(r + i, c, c + k - 1) != target:
                return False

        for j in range(k):
            if col_sum(c + j, r, r + k - 1) != target:
                return False

        d1 = 0
        d2 = 0
        for i in range(k):
            d1 += grid[r + i][c + i]
            d2 += grid[r + i][c + k - 1 - i]

        return d1 == target and d2 == target

    for k in range(min(m, n), 0, -1):
        for r in range(m - k + 1):
            for c in range(n - k + 1):
                if is_magic(r, c, k):
                    return k

    return 1

The code breaks down into three parts. First, it builds the row and column prefix sum arrays in a single pass. The rowPfx[r][c + 1] stores the cumulative sum along row r, and colPfx[r + 1][c] does the same down column c.

Second, two helper functions row_sum and col_sum use prefix sums to compute any contiguous row or column sum in O(1). This is the key optimization over brute force.

Third, is_magic checks whether a k x k subgrid starting at (r, c) is a magic square. It sets the target from the first row, then verifies every other row, every column, and both diagonals. The function returns early on the first mismatch.

The main loop iterates k from the largest possible value down to 1. It returns the first k for which any valid magic square exists. Since we check largest first, the first match is the answer.

Complexity analysis

The prefix sums reduce row and column sum lookups to O(1), but diagonal verification still costs O(k) per candidate. This makes the overall approach faster than pure brute force (which would have an extra factor of k for rows and columns), but not dramatically so. For the given constraints (m, n up to 50), this runs comfortably within time limits.

The building blocks

This problem relies on two core techniques:

1. Prefix sums for range queries: Precomputing cumulative sums so that any contiguous subarray sum can be computed in O(1). This is the same idea behind Range Sum Query 2D and appears in dozens of matrix problems.

2. Brute force with pruning from largest to smallest: Instead of finding all magic squares and picking the biggest, you search from the largest possible k downward and return immediately when you find a match. This "early exit" strategy avoids unnecessary work.

Edge cases

• 1x1 grid: every single cell is trivially a 1x1 magic square. Return 1.
• No magic square larger than 1: when no k >= 2 subgrid has matching sums, the answer is 1. Every cell is a valid 1x1 magic square by definition.
• Grid with all identical values: every subgrid is a magic square. Return min(m, n).
• Single row or single column: only 1x1 squares are possible. Return 1.

From understanding to recall

You have seen the approach: build prefix sums, iterate from the largest k downward, check each candidate. The logic is clear when you read it. But reproducing it in 20 minutes under interview pressure is a different skill.

The tricky parts are remembering to build both row and column prefix sums (not just one), handling the off-by-one indexing in the prefix arrays, and not forgetting the diagonal checks that cannot use prefix sums. These details are exactly the kind of thing that slips away without practice.

Spaced repetition locks them in. You solve this problem today, revisit it in three days, then a week later, then two weeks. Each rep is faster than the last. After a few rounds, the prefix sum setup and the nested k-r-c loop become automatic. That is how you turn understanding into reliable recall.

Related posts

• Range Sum Query 2D - The prefix sum foundation for matrix problems
• Set Matrix Zeroes - Another matrix traversal problem
• Maximal Square - Finding optimal subgrids in a matrix