Given an integer n and an n × n matrix, check whether the matrix is a Magic Square or not. A Magic Square is a matrix containing distinct elements from 1 to n * n such that the sum of every row, every column, and both diagonals is the same.
Examples:
Input: mat =
[[2, 7, 6],
[[9, 5, 1],
[4, 3, 8]]
Output: "Magic Square"
Explanation: R1->2+7+6=15, R2->9+5+1=15, R3->4+3+8=15
C1->2+9+4=15, C2->7+5+3=15, C3->6+1+8=15
D1->2+5+8=15, D2=6+5+4=15Input: mat = [[1, 2], [3, 4]]
Output: "Not a Magic Square"
Explanation: Sum of all rows and columns are not same.Input: mat = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Output: "Not a Magic Square"
Explanation: All sums are same but all elements from 1 to n2 are not present.
Try it on GfG Practice
Table of Content
[Naive Approach] Using Diagonal and Row-Column Sum Verification - O(n * n) Time and O(n * n) Space
- Use a boolean array to track visited items for uniqueness (all numbers from 1 to n*n should appear once)
- Compute sum of first row (let us call this sum as target) so that we can match it later with every row, column and diagonal
- Traverse the matrix and compute row and column sums and compare with the target. If not same, then return false. Also check if a visited item appears again, then return false.
- Traverse both diagonals and compare the sums with the target sum.
#include <iostream>
#include <vector>
using namespace std;
bool isMagicSquare(vector<vector<int>>& mat) {
int n = mat.size();
int target = 0;
// first row sum
for (int j = 0; j < n; j++)
target += mat[0][j];
// track uniqueness
vector<int> visited(n*n + 1, 0);
for (int i = 0; i < n; i++) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < n; j++) {
rowSum += mat[i][j];
colSum += mat[j][i];
int val = mat[i][j];
// range + duplicate check
if (val < 1 || val > n*n || visited[val])
return false;
visited[val] = 1;
}
if (rowSum != target || colSum != target)
return false;
}
int d1 = 0, d2 = 0;
// diagonals
for (int i = 0; i < n; i++) {
d1 += mat[i][i];
d2 += mat[i][n-i-1];
}
return d1 == target && d2 == target;
}
int main() {
vector<vector<int>> mat = {
{2,7,6},
{9,5,1},
{4,3,8}
};
cout << (isMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
return 0;
}
public class GFG {
public static boolean isMagicSquare(int[][] mat) {
int n = mat.length;
int target = 0;
// Compute target sum (first row)
for (int j = 0; j < n; j++)
target += mat[0][j];
// track values
int[] visited = new int[n*n + 1];
for (int i = 0; i < n; i++) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < n; j++) {
rowSum += mat[i][j];
colSum += mat[j][i];
int val = mat[i][j];
// check range + duplicate
if (val < 1 || val > n*n || visited[val] == 1)
return false;
visited[val] = 1;
}
// validate row & column
if (rowSum != target || colSum != target)
return false;
}
int d1 = 0, d2 = 0;
// diagonal sums
for (int i = 0; i < n; i++) {
d1 += mat[i][i];
d2 += mat[i][n-i-1];
}
return d1 == target && d2 == target;
}
public static void main(String[] args) {
int[][] mat = {{2,7,6},{9,5,1},{4,3,8}};
System.out.println(isMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
}
}
def is_magic_square(mat):
n = len(mat)
# first row sum
target = sum(mat[0])
# track values
visited = [0] * (n*n + 1)
for i in range(n):
row_sum = 0
col_sum = 0
for j in range(n):
row_sum += mat[i][j]
col_sum += mat[j][i]
val = mat[i][j]
# check range and duplicate
if val < 1 or val > n*n or visited[val]:
return False
visited[val] = 1
# validate row & column
if row_sum != target or col_sum != target:
return False
# diagonal sums
d1 = sum(mat[i][i] for i in range(n))
d2 = sum(mat[i][n-i-1] for i in range(n))
return d1 == target and d2 == target
if __name__ == "__main__":
mat = [[2,7,6],[9,5,1],[4,3,8]]
print("Magic Square" if is_magic_square(mat) else "Not a Magic Square")
using System;
class GFG
{
static bool IsMagicSquare(int[,] mat)
{
int n = mat.GetLength(0);
int target = 0;
// Compute target sum (first row)
for (int j = 0; j < n; j++)
target += mat[0, j];
// track values
int[] visited = new int[n*n + 1];
for (int i = 0; i < n; i++)
{
int rowSum = 0, colSum = 0;
for (int j = 0; j < n; j++)
{
rowSum += mat[i, j];
colSum += mat[j, i];
int val = mat[i, j];
// check valid range + duplicate
if (val < 1 || val > n*n || visited[val] == 1)
return false;
visited[val] = 1;
}
// validate row & column
if (rowSum != target || colSum != target)
return false;
}
int d1 = 0, d2 = 0;
// diagonal check
for (int i = 0; i < n; i++)
{
d1 += mat[i, i];
d2 += mat[i, n-i-1];
}
return d1 == target && d2 == target;
}
static void Main()
{
int[,] mat = {
{2,7,6},
{9,5,1},
{4,3,8}
};
Console.WriteLine(IsMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
}
}
function isMagicSquare(mat) {
let n = mat.length;
// first row sum
let target = mat[0].reduce((a, b) => a + b, 0);
// track values
let visited = new Array(n*n + 1).fill(0);
for (let i = 0; i < n; i++) {
let rowSum = 0, colSum = 0;
for (let j = 0; j < n; j++) {
rowSum += mat[i][j];
colSum += mat[j][i];
let val = mat[i][j];
// check range and duplicate
if (val < 1 || val > n*n || visited[val])
return false;
visited[val] = 1;
}
// validate row & column
if (rowSum !== target || colSum !== target)
return false;
}
let d1 = 0, d2 = 0;
// diagonal sums
for (let i = 0; i < n; i++) {
d1 += mat[i][i];
d2 += mat[i][n-i-1];
}
return d1 === target && d2 === target;
}
// Driver Code
let mat = [[2,7,6],[9,5,1],[4,3,8]];
console.log(isMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
Output
Magic Square
[Expected Approach] Using a Single Pass - O(n * n) Time and O(n * n) Space
This is mainly an optimization over the above approach. Instead of doing one more iteration for diagonals, we update diagonal sums during traversal when i == j and i + j == n - 1 . Note that all main diagonal elements have i == j and all other diagonal elements have i + j == n-1. One more optimization we make is, we can compute the target as n * (n*n + 1) / 2. For a magic square.
How does the sum formula work?
Sum of all numbers is 1 + 2 + 3, ... n2 which is equal to n2 × (n2 + 1)/2 [We have simply applied natural number sum formula for n = n2]. Now a magic square contains n divisions of the target sum (row wise or column wise sum), so we can write n x target = n2 × (n2 + 1)/2. From this expression, we can derive, target = n × (n2 + 1)/2
#include <iostream>
#include <vector>
using namespace std;
bool isMagicSquare(vector<vector<int>>& mat) {
int n = mat.size();
int target = n * (n*n + 1) / 2;
// track uniqueness
vector<int> visited(n*n + 1, 0);
int d1 = 0, d2 = 0;
for (int i = 0; i < n; i++) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < n; j++) {
int valRow = mat[i][j];
int valCol = mat[j][i];
// range + duplicate check
if (valRow < 1 || valRow > n*n || visited[valRow])
return false;
visited[valRow] = 1;
rowSum += valRow;
colSum += valCol;
// diagonals
if (i == j) d1 += valRow;
if (i + j == n - 1) d2 += valRow;
}
if (rowSum != target || colSum != target)
return false;
}
return d1 == target && d2 == target;
}
int main() {
vector<vector<int>> mat = {
{2,7,6},
{9,5,1},
{4,3,8}
};
cout << (isMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
return 0;
}
import java.util.Scanner;
public class GFG {
static boolean isMagicSquare(int[][] mat) {
int n = mat.length;
int target = n * (n*n + 1) / 2;
boolean[] visited = new boolean[n*n + 1];
int d1 = 0, d2 = 0;
for (int i = 0; i < n; i++) {
int rowSum = 0, colSum = 0;
for (int j = 0; j < n; j++) {
int valRow = mat[i][j];
int valCol = mat[j][i];
// range + duplicate check
if (valRow < 1 || valRow > n*n || visited[valRow])
return false;
visited[valRow] = true;
rowSum += valRow;
colSum += valCol;
// diagonals
if (i == j) d1 += valRow;
if (i + j == n - 1) d2 += valRow;
}
if (rowSum != target || colSum != target)
return false;
}
return d1 == target && d2 == target;
}
public static void main(String[] args) {
int[][] mat = {
{2,7,6},
{9,5,1},
{4,3,8}
};
System.out.println(isMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
}
}
def is_magic_square(mat):
n = len(mat)
target = n * (n*n + 1) // 2
visited = [0] * (n*n + 1)
d1 = d2 = 0
for i in range(n):
row_sum = col_sum = 0
for j in range(n):
val_row = mat[i][j]
val_col = mat[j][i]
# range + duplicate check
if val_row < 1 or val_row > n*n or visited[val_row]:
return False
visited[val_row] = 1
row_sum += val_row
col_sum += val_col
# diagonals
if i == j:
d1 += val_row
if i + j == n - 1:
d2 += val_row
if row_sum != target or col_sum != target:
return False
return d1 == target and d2 == target
if __name__ == "__main__":
mat = [
[2,7,6],
[9,5,1],
[4,3,8]
]
print("Magic Square" if is_magic_square(mat) else "Not a Magic Square")
using System;
class GFG
{
static bool IsMagicSquare(int[,] mat)
{
int n = mat.GetLength(0);
int target = 0;
// Compute target sum (first row)
for (int j = 0; j < n; j++)
target += mat[0, j];
// track values
int[] visited = new int[n*n + 1];
for (int i = 0; i < n; i++)
{
int rowSum = 0, colSum = 0;
for (int j = 0; j < n; j++)
{
rowSum += mat[i, j];
colSum += mat[j, i];
int val = mat[i, j];
// check valid range + duplicate
if (val < 1 || val > n*n || visited[val] == 1)
return false;
visited[val] = 1;
}
// validate row & column
if (rowSum != target || colSum != target)
return false;
}
int d1 = 0, d2 = 0;
// diagonal check
for (int i = 0; i < n; i++)
{
d1 += mat[i, i];
d2 += mat[i, n-i-1];
}
return d1 == target && d2 == target;
}
static void Main()
{
int[,] mat = {
{2,7,6},
{9,5,1},
{4,3,8}
};
Console.WriteLine(IsMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
}
}
function isMagicSquare(mat) {
const n = mat.length;
const target = n * (n*n + 1) / 2;
const visited = new Array(n*n + 1).fill(false);
let d1 = 0, d2 = 0;
for (let i = 0; i < n; i++) {
let rowSum = 0, colSum = 0;
for (let j = 0; j < n; j++) {
let valRow = mat[i][j];
let valCol = mat[j][i];
// range + duplicate check
if (valRow < 1 || valRow > n*n || visited[valRow])
return false;
visited[valRow] = true;
rowSum += valRow;
colSum += valCol;
// diagonals
if (i === j) d1 += valRow;
if (i + j === n - 1) d2 += valRow;
}
// validate row & column
if (rowSum !== target || colSum !== target)
return false;
}
return d1 === target && d2 === target;
}
// Driver Code
const mat = [
[2,7,6],
[9,5,1],
[4,3,8]
];
console.log(isMagicSquare(mat) ? "Magic Square" : "Not a Magic Square");
Output
Magic Square