🧩 Beginner-Friendly Guide 'Largest Magic Square' – LeetCode 1895 (C++, Python, JavaScript)

Source: Dev.to

Problem Statement

Searching for patterns in a grid is a classic challenge in algorithmic thinking.
In this problem we are tasked with finding the largest possible sub‑grid where every row, column, and both main diagonals add up to the exact same value.

You’re given

• An m × n integer grid.
• A Magic Square is a k × k sub‑grid where the sum of every row, every column, and both diagonals are equal.

Your goal

Return the maximum side length k of any magic square hidden within the grid.

Examples

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 size 3. Every row sum, column sum, and diagonal sum of this square equals 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] ≤ 10⁶

Intuition

A brute‑force solution would check every possible square of every size and manually sum its rows, columns, and diagonals. This repeats a lot of work.

To make it efficient we use prefix sums (running totals).
If we know the total of a row up to column 10 and up to column 5, the sum between 5 and 10 is just their difference.

We pre‑compute four prefix‑sum tables for every cell:

With these tables, checking whether a k × k square is magic reduces to a few constant‑time subtractions.
We search from the largest possible side length min(m, n) downwards; the first size that satisfies the condition is the answer.

Solution Code

C++

class Solution {
public:
    // Check whether the k×k square with top‑left corner (r, c) is magic
    bool isMagic(const vector>>& pref,
                 int r, int c, int k) {
        // target sum = main diagonal of the square
        int target = pref[r + k][c + k][2] - pref[r][c][2];

        // anti‑diagonal must match
        if (target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3])
            return false;

        // each row sum must match
        for (int i = r; i >& grid) {
        int m = grid.size(), n = grid[0].size();

        // pref[i][j] = {row, col, diag, anti‑diag} sums up to (i‑1, j‑1)
        vector>> pref(m + 1,
                                          vector>(n + 2, {0,0,0,0}));

        for (int i = 1; i = 2; --k) {
            for (int i = 0; i + k  int:
        m, n = len(grid), len(grid[0])

        # pref[i][j] = [row, col, diag, anti_diag] sums up to (i‑1, j‑1)
        # extra padding (n+2) simplifies anti‑diagonal indexing
        pref = [[[0] * 4 for _ in range(n + 2)] for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                val = grid[i - 1][j - 1]
                pref[i][j][0] = pref[i][j - 1][0] + val          # row
                pref[i][j][1] = pref[i - 1][j][1] + val          # column
                pref[i][j][2] = pref[i - 1][j - 1][2] + val      # main diagonal
                pref[i][j][3] = pref[i - 1][j + 1][3] + val      # anti‑diagonal

        # helper to test a k×k square with top‑left corner (r, c)
        def is_magic(r: int, c: int, k: int) -> bool:
            target = pref[r + k][c + k][2] - pref[r][c][2]      # main diagonal
            if target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3]:
                return False

            # rows
            for i in range(r, r + k):
                if pref[i + 1][c + k][0] - pref[i + 1][c][0] != target:
                    return False
            # columns
            for j in range(c, c + k):
                if pref[r + k][j + 1][1] - pref[r][j + 1][1] != target:
                    return False
            return True

        for k in range(min(m, n), 1, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if is_magic(i, j, k):
                        return k
        return 1

Python

3] + val

def is_magic(r, c, k):
    # Target sum from the main diagonal
    target = pref[r + k][c + k][2] - pref[r][c][2]

    # Check anti-diagonal
    if target != pref[r + k][c + 1][3] - pref[r][c + k + 1][3]:
        return False

    # Check all rows
    for i in range(r, r + k):
        if pref[i + 1][c + k][0] - pref[i + 1][c][0] != target:
            return False

    # Check all columns
    for j in range(c, c + k):
        if pref[r + k][j + 1][1] - pref[r][j + 1][1] != target:
            return False

    return True

# Check from largest possible side length downwards
for k in range(min(m, n), 1, -1):
    for i in range(m - k + 1):
        for j in range(n - k + 1):
            if is_magic(i, j, k):
                return k
return 1

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestMagicSquare = function (grid) {
    const m = grid.length;
    const n = grid[0].length;

    // Create prefix

How It Works – Step‑by‑Step

1. Build prefix tables – O(m·n) time, O(m·n) extra space.
2. Iterate side lengths from large to small.
3. For each possible top‑left corner, extract:
   • main diagonal sum,
   • anti‑diagonal sum,
   • each row sum,
   • each column sum
     using only constant‑time subtractions of the prefix tables.
4. The first size that passes all checks is the answer.

Because we stop at the first valid size, the overall complexity is
O(m·n·min(m, n)) in the worst case (still fast for m, n ≤ 50).