Largest Magic Square

Medium
1567.

Largest Magic Square

Largest Magic Square is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon and Google interviews.

A k x k magic square is a square block of numbers in which every row sum, every column sum and both diagonal sums are all equal. The numbers need not be distinct, and every 1 x 1 block is trivially a magic square.

Given an m x n integer matrix grid, return the side length k of the largest magic square that appears as a contiguous k x k sub-grid of grid.

Example 1

Input
grid = [[3,8,1,6],[1,3,5,7],[2,4,9,2]]
Output
3
Explanation
Columns 1–3 hold the classic 3 × 3 magic square: every row, column and diagonal sums to 15.

Example 2

Input
grid = [[5,1,3],[2,3,3],[1,3,3]]
Output
2
Explanation
The bottom-right block `[[3,3],[3,3]]` is magic; the whole grid is not.

Example 3

Input
grid = [[1,2],[3,4]]
Output
1

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestMagicSquare = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Magic Square — Solution in Python, Java & C++

Largest Magic Square solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Largest Magic Square is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A k x k magic square is a square block of numbers in which every row sum, every column sum and both diagonal sums are all equal. The numbers need not be distinct, and every 1 x 1 block is trivially a magic square.

Given an m x n integer matrix grid, return the side length k of the largest magic square that appears as a contiguous k x k sub-grid of grid.

Example 1

Input: grid = [[3,8,1,6],[1,3,5,7],[2,4,9,2]]
Output: 3
Explanation: Columns 1–3 hold the classic 3 × 3 magic square: every row, column and diagonal sums to 15.

Example 2

Input: grid = [[5,1,3],[2,3,3],[1,3,3]]
Output: 2
Explanation: The bottom-right block `[[3,3],[3,3]]` is magic; the whole grid is not.

Example 3

Input: grid = [[1,2],[3,4]]
Output: 1

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 10^6

Hints for Largest Magic Square

  1. Hint 1

    Try sizes from largest to smallest; the first size that has a magic square anywhere is the answer, and size 1 always works.

  2. Hint 2

    Prefix sums along every row and every column turn each row or column sum of a block into one subtraction.

  3. Hint 3

    For a candidate block, compare all k row sums and k column sums with the first row's sum, then compute the two diagonals directly.

How to solve Largest Magic Square

Check every block, largest sizes first, with row and column prefix sums making each line sum O(1).

Approach

  1. Build rowP[i][j] = sum of grid[i][0..j-1] and colP[i][j] = sum of grid[0..i-1][j].
  2. For k from min(m, n) down to 2, for every top-left (r, c) with the block inside the grid:
  3. Let target be the block's first row sum. Every row sum rowP[r+t][c+k] - rowP[r+t][c] and column sum colP[r+k][c+t] - colP[r][c+t] must equal it; stop early on a mismatch.
  4. Add up both diagonals directly; if they also equal target, return k.
  5. If no block of size 2 or more is magic, return 1.

Why it works

The search is exhaustive over sizes and positions, and it checks exactly the definition: all rows, all columns and both diagonals of the block have one common sum. Scanning sizes downwards means the first hit is the largest.

Complexity

  • Time — O(m · n · min(m, n)²)
  • Space — O(m · n)

Pitfalls

  • Both diagonals must match, not just the rows and columns.
  • Every 1 x 1 block is magic, so the answer is at least 1.
  • Values reach 10^6 and a line has up to 50 of them — 5 × 10^7 still fits in 32 bits.

Reference solution

Python

from typing import List

def largestMagicSquare(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    row_p = [[0] * (n + 1) for _ in range(m)]
    col_p = [[0] * n for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            row_p[i][j + 1] = row_p[i][j] + grid[i][j]
            col_p[i + 1][j] = col_p[i][j] + grid[i][j]
    for k in range(min(m, n), 1, -1):
        for r in range(m - k + 1):
            for c in range(n - k + 1):
                target = row_p[r][c + k] - row_p[r][c]
                ok = True
                for t in range(k):
                    if row_p[r + t][c + k] - row_p[r + t][c] != target or col_p[r + k][c + t] - col_p[r][c + t] != target:
                        ok = False
                        break
                if not ok:
                    continue
                d1 = sum(grid[r + t][c + t] for t in range(k))
                d2 = sum(grid[r + t][c + k - 1 - t] for t in range(k))
                if d1 == target and d2 == target:
                    return k
    return 1

Java

public static int largestMagicSquare(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] rowP = new int[m][n + 1], colP = new int[m + 1][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            rowP[i][j + 1] = rowP[i][j] + grid[i][j];
            colP[i + 1][j] = colP[i][j] + grid[i][j];
        }
    }
    for (int k = Math.min(m, n); k >= 2; k--) {
        for (int r = 0; r + k <= m; r++) {
            for (int c = 0; c + k <= n; c++) {
                int target = rowP[r][c + k] - rowP[r][c];
                boolean ok = true;
                for (int t = 0; t < k && ok; t++) {
                    if (rowP[r + t][c + k] - rowP[r + t][c] != target) ok = false;
                    else if (colP[r + k][c + t] - colP[r][c + t] != target) ok = false;
                }
                if (!ok) continue;
                int d1 = 0, d2 = 0;
                for (int u = 0; u < k; u++) { d1 += grid[r + u][c + u]; d2 += grid[r + u][c + k - 1 - u]; }
                if (d1 == target && d2 == target) return k;
            }
        }
    }
    return 1;
}

C++

int largestMagicSquare(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> rowP(m, vector<int>(n + 1, 0)), colP(m + 1, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            rowP[i][j + 1] = rowP[i][j] + grid[i][j];
            colP[i + 1][j] = colP[i][j] + grid[i][j];
        }
    }
    for (int k = min(m, n); k >= 2; k--) {
        for (int r = 0; r + k <= m; r++) {
            for (int c = 0; c + k <= n; c++) {
                int target = rowP[r][c + k] - rowP[r][c];
                bool ok = true;
                for (int t = 0; t < k && ok; t++) {
                    if (rowP[r + t][c + k] - rowP[r + t][c] != target) ok = false;
                    else if (colP[r + k][c + t] - colP[r][c + t] != target) ok = false;
                }
                if (!ok) continue;
                int d1 = 0, d2 = 0;
                for (int u = 0; u < k; u++) { d1 += grid[r + u][c + u]; d2 += grid[r + u][c + k - 1 - u]; }
                if (d1 == target && d2 == target) return k;
            }
        }
    }
    return 1;
}

JavaScript

var largestMagicSquare = function(grid) {
    var m = grid.length, n = grid[0].length, i, j;
    var rowP = [], colP = [];
    for (i = 0; i < m; i++) rowP.push(new Array(n + 1).fill(0));
    for (i = 0; i <= m; i++) colP.push(new Array(n).fill(0));
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            rowP[i][j + 1] = rowP[i][j] + grid[i][j];
            colP[i + 1][j] = colP[i][j] + grid[i][j];
        }
    }
    for (var k = Math.min(m, n); k >= 2; k--) {
        for (var r = 0; r + k <= m; r++) {
            for (var c = 0; c + k <= n; c++) {
                var target = rowP[r][c + k] - rowP[r][c], ok = true;
                for (var t = 0; t < k && ok; t++) {
                    if (rowP[r + t][c + k] - rowP[r + t][c] !== target) ok = false;
                    else if (colP[r + k][c + t] - colP[r][c + t] !== target) ok = false;
                }
                if (!ok) continue;
                var d1 = 0, d2 = 0;
                for (var u = 0; u < k; u++) { d1 += grid[r + u][c + u]; d2 += grid[r + u][c + k - 1 - u]; }
                if (d1 === target && d2 === target) return k;
            }
        }
    }
    return 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal