We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Magic Squares In Grid

Difficulty: Medium

Problem Description

Given a 3 x 3 grid filled with distinct numbers from 1 to 9, how many 3 x 3 magic square subgrids exist in a given row x col grid of integers? A magic square is defined as a grid where each row, column, and both diagonals all have the same sum.

Key Insights

  • A valid magic square must contain distinct numbers from 1 to 9.
  • The sum for each row, column, and diagonal in a 3 x 3 magic square should be 15.
  • The grid can contain numbers from 0 to 15, but only the numbers 1 to 9 are considered for forming a magic square.
  • The maximum number of 3 x 3 subgrids in a grid is restricted by its dimensions (row-2) x (col-2).

Space and Time Complexity

Time Complexity: O((row-2) * (col-2))
Space Complexity: O(1)

Solution

To solve the problem, we will iterate through each possible 3 x 3 subgrid within the input grid. For each subgrid, we will:

  1. Check if all numbers are distinct and within the range 1 to 9.
  2. Calculate the sum of each row, column, and the two diagonals to verify if they equal 15.
  3. Count how many valid magic squares we find.

The approach primarily uses nested loops to traverse the grid and a set to check for distinct values.

Code Solutions

def numMagicSquaresInside(grid):
    if len(grid) < 3 or len(grid[0]) < 3:
        return 0

    def isMagicSquare(x, y):
        nums = set()
        for i in range(3):
            for j in range(3):
                num = grid[x + i][y + j]
                if num < 1 or num > 9 or num in nums:
                    return False
                nums.add(num)

        return (grid[x][y] + grid[x][y + 1] + grid[x][y + 2] == 15 and
                grid[x + 1][y] + grid[x + 1][y + 1] + grid[x + 1][y + 2] == 15 and
                grid[x + 2][y] + grid[x + 2][y + 1] + grid[x + 2][y + 2] == 15 and
                grid[x][y] + grid[x + 1][y] + grid[x + 2][y] == 15 and
                grid[x][y + 1] + grid[x + 1][y + 1] + grid[x + 2][y + 1] == 15 and
                grid[x][y + 2] + grid[x + 1][y + 2] + grid[x + 2][y + 2] == 15 and
                grid[x][y] + grid[x + 1][y + 1] + grid[x + 2][y + 2] == 15 and
                grid[x + 2][y] + grid[x + 1][y + 1] + grid[x][y + 2] == 15)

    count = 0
    for i in range(len(grid) - 2):
        for j in range(len(grid[0]) - 2):
            if isMagicSquare(i, j):
                count += 1
    return count
← Back to All Questions