How do you solve Magic Squares In Grid on LeetCode?

Magic Squares In Grid (LeetCode #840) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: A magic square must contain distinct numbers from 1 to 9.

What is the brute force solution for Magic Squares In Grid?

The brute force approach for Magic Squares In Grid is Brute Force, with O(n²) time complexity and O(1) space complexity. We can check every possible 3x3 subgrid in the given grid to see if it forms a magic square. This involves iterating through the grid and validating each subgrid individually. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Magic Squares In Grid?

Magic Squares In Grid uses the following concepts: Array, Hash Table, Math, Matrix. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Magic Squares In Grid?

Always validate your assumptions about the input data. Consider edge cases, such as grids smaller than 3x3. Discuss your thought process clearly while coding.

What are common mistakes when solving Magic Squares In Grid?

Not checking for distinct numbers in the subgrid. Overlooking the specific sum required for a magic square.

#840

Magic Squares In Grid

Medium

ArrayHash TableMathMatrixHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

Instead of checking every possible 3x3 subgrid, we can use a predefined set of valid magic squares and check if the current 3x3 grid matches any of them. This reduces the number of checks significantly.

⚙️

Algorithm

3 steps

1Step 1: Define a list of all possible 3x3 magic squares.
2Step 2: Iterate through each possible starting point for a 3x3 subgrid in the grid.
3Step 3: For each starting point, extract the 3x3 subgrid and check if it matches any of the predefined magic squares.

solution.py12 lines

1def numMagicSquaresInside(grid):
2    magic_squares = [
3        [8, 1, 6], [6, 1, 8], [4, 9, 2], [2, 9, 4],
4        [8, 3, 4], [4, 3, 8], [6, 7, 2], [2, 7, 6]
5    ]
6    count = 0
7    for i in range(len(grid) - 2):
8        for j in range(len(grid[0]) - 2):
9            square = [row[j:j+3] for row in grid[i:i+3]]
10            if square in magic_squares:
11                count += 1
12    return count

ℹ

Complexity note: The time complexity remains O(n²) since we still check each possible 3x3 grid, but the checks are faster because we compare against a fixed set of magic squares. The space complexity is O(1) since we only store the magic squares.

1A magic square must contain distinct numbers from 1 to 9.
2The sum of each row, column, and diagonal in a magic square must equal 15.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.