Magic Squares In Grid - Leetcode Solution

Problem:

Given an N x N grid containing only integers 1 through N^2, find whether there exists a magical string S of length N^2 such that converting any substring of S into a square grid with side length N will result in a valid magic square.

Example: Input: [[4,3,8,4], [9,5,1,9], [2,7,6,2]]

Output: True

Explanation: The numbers in the given 3x3 grid forms a magical string S of length 9 as follows: 4 3 8 9 5 1 2 7 6 Converting any substring of S into a square grid with side length 3 will result in a valid magic square.

Solution: The problem can be solved using the brute force approach where we generate all the possible substrings of length N^2 and check if they form a magic square when reshaped into an N x N matrix. However, this approach has a very high time complexity and is not efficient for larger values of N.

A better approach is to observe the properties of a magic square and check if the given grid satisfies those properties. A magic square is a square grid with side length N where the sum of every row, column, and diagonal is the same. We can use this property to check if the given grid forms a magic square or not.

To check if the given grid forms a magic square, we can follow these steps:

1. Calculate the sum of the first row and store it in a variable called expected_sum.
2. Check if the sum of every row in the grid is equal to expected_sum.
3. Check if the sum of every column in the grid is equal to expected_sum.
4. Check if the sum of the main diagonal is equal to expected_sum.
5. Check if the sum of the secondary diagonal is equal to expected_sum.

If all these conditions are satisfied, then the given grid forms a magic square.

Let's see the Python implementation of the above approach.

Code:

class Solution: def isMagicSquare(self, grid: List[List[int]]) -> bool: #calculate the expected sum expected_sum = sum(grid[0])

    #check if the sum of every row is equal to expected_sum
    for row in grid:
        if sum(row) != expected_sum:
            return False
    
    #check if the sum of every column is equal to expected_sum
    for col in range(len(grid)):
        col_sum = 0
        for row in range(len(grid)):
            col_sum += grid[row][col]
        if col_sum != expected_sum:
            return False
    
    #check if the sum of the main diagonal is equal to expected_sum
    diagonal_sum = 0
    for i in range(len(grid)):
        diagonal_sum += grid[i][i]
    if diagonal_sum != expected_sum:
        return False
    
    #check if the sum of the secondary diagonal is equal to expected_sum
    diagonal_sum = 0
    for i in range(len(grid)):
        diagonal_sum += grid[i][len(grid)-i-1]
    if diagonal_sum != expected_sum:
        return False
    
    return True

Time Complexity: O(N^2) because we are iterating over the entire grid to calculate the sum of rows, columns, and diagonals.

Space Complexity: O(1) because we are not using any extra space and all the variables used are constant irrespective of the size of the input.

1