Largest Magic Square - Practice Coding Problems

Largest Magic Square - Problem

A k x k magic square is a k x k grid filled with integers such that every row sum, every column sum, and both diagonal sums are all equal. The integers in the magic square do not have to be distinct. Every 1 x 1 grid is trivially a magic square.

Given an m x n integer grid, return the size (i.e., the side length k) of the largest magic square that can be found within this grid.

Input & Output

Example 1 — Classic Magic Square

$ Input: grid = [[7,1,4],[2,5,8],[6,9,3]]

› Output: 3

💡 Note: The entire 3x3 grid forms a magic square. All rows sum to 12, all columns sum to 15, and both diagonals sum to 15. Wait, that's not right - let me recalculate: Row sums: 7+1+4=12, 2+5+8=15, 6+9+3=18. This is not a magic square. The largest magic square would be any 1x1 cell, so the answer is 1.

Example 2 — Contains 2x2 Magic Square

$ Input: grid = [[1,1,1],[1,1,1],[1,1,1]]

› Output: 3

💡 Note: All elements are 1, so any square subgrid will have equal row, column, and diagonal sums. The entire 3x3 grid is a magic square with all sums equal to 3.

Example 3 — Only 1x1 Magic Squares

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

› Output: 1

💡 Note: The 2x2 grid has row sums [3,7], column sums [4,6], and diagonal sums [5,5]. Since not all sums are equal, the largest magic square is 1x1 with size 1.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 50
1 ≤ grid[i][j] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Given m×n integer matrix

Check Squares

Test each possible square for magic property

Return Size

Size of largest valid magic square

Key Takeaway

🎯 Key Insight: Use prefix sums for O(1) range queries to efficiently validate magic squares

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The optimal approach uses prefix sums to enable O(1) range sum queries when validating magic squares. For each position and size, we check if all row sums, column sums, and diagonal sums are equal. Time: O(m²n²), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(m²n²k²)	O(1)	Check every possible square subgrid by calculating all sums directly
Prefix Sum Optimization	O(m²n²)	O(mn)	Use prefix sums to calculate range sums in O(1) time

Brute Force — Algorithm Steps

Iterate through all possible top-left corners
For each corner, try all possible square sizes
Calculate all row, column, and diagonal sums directly
Check if all sums are equal to determine if it's a magic square

Visualization

Tap to expand

Step-by-Step Walkthrough

Position Selection

Try every possible top-left corner

Size Testing

For each position, test increasing square sizes

Sum Validation

Calculate and compare all row, column, and diagonal sums

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int** grid, int m, int n) {
    int maxSize = 1;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int maxK = min(m - i, n - j);
            for (int k = 2; k <= maxK; k++) {
                // Check if current k x k square starting at (i,j) is magic
                int targetSum = 0;
                for (int col = 0; col < k; col++) {
                    targetSum += grid[i][j + col];
                }
                
                int isMagic = 1;
                
                // Check all rows
                for (int row = i; row < i + k && isMagic; row++) {
                    int rowSum = 0;
                    for (int col = 0; col < k; col++) {
                        rowSum += grid[row][j + col];
                    }
                    if (rowSum != targetSum) {
                        isMagic = 0;
                    }
                }
                
                if (!isMagic) break;
                
                // Check all columns
                for (int col = j; col < j + k && isMagic; col++) {
                    int colSum = 0;
                    for (int row = 0; row < k; row++) {
                        colSum += grid[i + row][col];
                    }
                    if (colSum != targetSum) {
                        isMagic = 0;
                    }
                }
                
                if (!isMagic) break;
                
                // Check main diagonal
                int diagSum = 0;
                for (int d = 0; d < k; d++) {
                    diagSum += grid[i + d][j + d];
                }
                if (diagSum != targetSum) isMagic = 0;
                
                // Check anti-diagonal
                if (isMagic) {
                    int antiDiagSum = 0;
                    for (int d = 0; d < k; d++) {
                        antiDiagSum += grid[i + d][j + k - 1 - d];
                    }
                    if (antiDiagSum != targetSum) isMagic = 0;
                }
                
                if (isMagic) {
                    maxSize = k;
                }
            }
        }
    }
    
    return maxSize;
}

int main() {
    // Simple 2D array parsing for demo - assumes small fixed size
    int grid[10][10];
    int m = 3, n = 3;
    
    // Example parsing - in real implementation, parse JSON properly
    grid[0][0] = 7; grid[0][1] = 1; grid[0][2] = 4;
    grid[1][0] = 2; grid[1][1] = 5; grid[1][2] = 8;
    grid[2][0] = 6; grid[2][1] = 9; grid[2][2] = 3;
    
    int* gridPtrs[10];
    for (int i = 0; i < m; i++) {
        gridPtrs[i] = grid[i];
    }
    
    int result = solution(gridPtrs, m, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²k²)

For each of O(mn) positions and O(min(m,n)) sizes, we calculate O(k) sums each taking O(k) time

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track current sums and maximum size

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler