LeetCode Solutions Blog

Magic Squares In Grid

Number: 870

Difficulty: Medium

Paid? No

Problem Description

Given a 2D grid of integers, return the number of 3 x 3 subgrids that form a magic square. A 3 x 3 magic square is a grid filled with distinct numbers from 1 to 9 so that every row, every column, and both diagonals sum up to the same number.

Key Insights

Every valid 3 x 3 magic square must use each number from 1 to 9 exactly once.
The magic sum of any row, column, or diagonal in a 3 x 3 magic square is 15.
Given the grid size limits, a brute-force scan over all possible 3 x 3 subgrids is efficient.
Checking a subgrid involves verifying the distinctness and range of numbers along with the sum constraints for rows, columns, and diagonals.

Space and Time Complexity

Time Complexity: O(n*m), where n is the number of rows and m is the number of columns. Space Complexity: O(1) extra space.

Solution

We iterate over each possible 3 x 3 subgrid in the given grid. For each subgrid, we first verify that all numbers are between 1 and 9 and that they are distinct. Then, we check that the sum of each row, column, and the two main diagonals equals 15. If all conditions hold, we count that subgrid as a magic square. The solution uses a brute-force approach with nested loops over the grid and constant-time checks for each subgrid.

Code Solutions

# Function to count magic squares in a grid.
def numMagicSquaresInside(grid):
    # Function to check if a 3x3 grid starting at (i, j) is a magic square.
    def isMagic(i, j):
        s = [grid[i + x][j + y] for x in range(3) for y in range(3)]
        # Check that numbers are between 1 and 9 and are unique.
        if sorted(s) != list(range(1, 10)):
            return False
        
        # Calculate rows, columns, and diagonals sums.
        if grid[i][j] + grid[i][j+1] + grid[i][j+2] != 15:
            return False
        if grid[i+1][j] + grid[i+1][j+1] + grid[i+1][j+2] != 15:
            return False
        if grid[i+2][j] + grid[i+2][j+1] + grid[i+2][j+2] != 15:
            return False
        
        if grid[i][j] + grid[i+1][j] + grid[i+2][j] != 15:
            return False
        if grid[i][j+1] + grid[i+1][j+1] + grid[i+2][j+1] != 15:
            return False
        if grid[i][j+2] + grid[i+1][j+2] + grid[i+2][j+2] != 15:
            return False
        
        if grid[i][j] + grid[i+1][j+1] + grid[i+2][j+2] != 15:
            return False
        if grid[i][j+2] + grid[i+1][j+1] + grid[i+2][j] != 15:
            return False
        
        return True

    count = 0
    rows = len(grid)
    cols = len(grid[0])
    # Iterate through each 3x3 subgrid possible.
    for i in range(rows - 2):
        for j in range(cols - 2):
            if isMagic(i, j):
                count += 1
    return count

# Example Usage:
# grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
# print(numMagicSquaresInside(grid))  # Output: 1