algoadvance

You are given an n x n grid of integers grid, where 1 <= grid[i][j] <= 9. We define a magic square subgrid as a 3 x 3 subgrid that contains all the numbers from 1 to 9 exactly once, and the sums of each row, column, and both diagonals are all equal.

Return the number of magic square subgrids that are contained in grid.

Example:

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

Constraints:

Clarifying Questions

  1. Can the grid be non-square (e.g., 3x4)?
    • No, the grid will always be square as per the constraints.
  2. Is the 3x3 subgrid always a subset of the original grid or can it be the entire grid?
    • The 3x3 subgrid is always a subset of the original grid. However, in the edge case where n == 3, the entire grid can be the only 3x3 subgrid.

Strategy

  1. Iterate through every possible top-left coordinate of a 3x3 subgrid in the given grid, ensuring we don’t go out of bounds.
  2. For each 3x3 subgrid, check the following conditions to determine if it’s a magic square:
    • It contains all numbers from 1 to 9.
    • All rows, columns, and diagonals sum to the same value.
  3. Count and return the number of such magic squares.

Code

def is_magic_square(grid, row, col):
    nums = set()
    for i in range(3):
        for j in range(3):
            num = grid[row + i][col + j]
            if num < 1 or num > 9:
                return False
            nums.add(num)
    
    if len(nums) != 9:
        return False
     
    s = sum(grid[row][col:col+3])  # Sum of the first row
    
    # Check rows
    for i in range(3):
        if sum(grid[row + i][col:col + 3]) != s:
            return False
    
    # Check columns
    for j in range(3):
        if sum(grid[row + i][col + j] for i in range(3)) != s:
            return False
    
    # Check diagonals
    if (grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2] != s or
        grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col] != s):
        return False
    
    return True

def numMagicSquaresInside(grid):
    n = len(grid)
    if n < 3:
        return 0
    
    count = 0
    
    for row in range(n - 2):
        for col in range(n - 2):
            if is_magic_square(grid, row, col):
                count += 1
    
    return count

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

Time Complexity

The time complexity for this solution is O(n^2), where n is the dimension of the original square grid. This is because we iterate through every possible top-left position of a 3x3 subgrid, and for each such subgrid, we perform a fixed amount of work (i.e., checking if it’s a magic square).

Given the constraint 1 <= n <= 10, this approach will work efficiently within the provided limits.

Try our interview co-pilot at AlgoAdvance.com