Check Given Matrix is magic square or not

Here is the structured documentation for the GeeksforGeeks Problem: Magic Square following your preferred format:

Problem Link

Magic Square – GeeksforGeeks

Problem: Magic Square

Problem Statement

Given an n × n matrix mat[][], check whether the matrix is a Magic Square.

A Magic Square is a matrix that satisfies two conditions:

1. It contains distinct elements from 1 to n².

2. The sum of every row, every column, and both main diagonals is the same.

Return "Magic Square" if the matrix satisfies both conditions, otherwise return "Not a Magic Square".

Examples

Example 1
Input: mat = [[2, 7, 6], [9, 5, 1], [4, 3, 8]]
Output: "Magic Square"
Explanation:

• All rows, columns, and diagonals sum to 15.

• All numbers from 1 to 9 are present.

Example 2
Input: mat = [[1, 2], [3, 4]]
Output: "Not a Magic Square"
Explanation:

• The sums of rows and columns are not equal.

Example 3
Input: mat = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Output: "Not a Magic Square"
Explanation:

• Although all sums are equal, the matrix does not have all distinct numbers from 1 to 9.

Constraints

• 1 <= mat.length <= 1000

• Matrix is always square (n x n)

Intuition

A matrix can only be a magic square if:

• All numbers from 1 to n² are present exactly once.

• All rows, columns, and both diagonals have the same sum.

First, compute the expected sum:

Then verify the sum of each row, column, and both diagonals. Also, validate the presence of all distinct numbers from 1 to n².

Approach

1. Calculate compVal = target sum for all rows/cols/diagonals.

2. Compute and compare the sum of:

   • Primary diagonal

   • Secondary diagonal

   • Each row

   • Each column

3. Return "Magic Square" if all checks pass, else return "Not a Magic Square".

Note: The given solution misses the check for distinct numbers from 1 to n², which is a required condition for a magic square.

Code (Java)

class Solution {
    public static String magicSquare(int mat[][]) {
        String isA = "Magic Square";
        String notA = "Not a Magic Square";
        int n = mat.length;
        int totalNum = n * n;
        int compVal = ((totalNum * (totalNum + 1)) / 2) / n;

        // Check diagonals
        int fDSum = 0, rDSum = 0;
        for (int i = 0; i < n; i++) {
            fDSum += mat[i][i];
            rDSum += mat[i][n - i - 1];
        }
        if (fDSum != compVal || rDSum != compVal) return notA;

        // Check rows
        for (int i = 0; i < n; i++) {
            int row = 0;
            for (int j = 0; j < n; j++) {
                row += mat[i][j];
            }
            if (row != compVal) return notA;
        }

        // Check columns (fixing original mistake)
        for (int j = 0; j < n; j++) {
            int col = 0;
            for (int i = 0; i < n; i++) {
                col += mat[i][j];
            }
            if (col != compVal) return notA;
        }

        // Optional: Check distinctness from 1 to n^2
        boolean[] seen = new boolean[totalNum + 1];
        for (int[] row : mat) {
            for (int val : row) {
                if (val < 1 || val > totalNum || seen[val]) return notA;
                seen[val] = true;
            }
        }

        return isA;
    }
}

Time and Space Complexity

• Time Complexity: O(n²)
  All rows, columns, and diagonals are traversed once. Distinct check is also O(n²).

• Space Complexity: O(n²) (for the distinctness check array)

Dry Run

Input: mat = [[2,7,6],[9,5,1],[4,3,8]], n = 3

• compVal = (9 * 10) / 2 / 3 = 15

• Primary Diagonal: 2 + 5 + 8 = 15

• Secondary Diagonal: 6 + 5 + 4 = 15

• Rows: All sum to 15

• Columns: All sum to 15

• Numbers from 1 to 9 are present exactly once → Return "Magic Square"

Conclusion

This problem combines matrix traversal with basic arithmetic and validation logic. A complete solution must not only check the sums of rows/columns/diagonals but also verify that all numbers from 1 to n² are distinct and present once.