LeetCode 840 - Magic Squares In Grid

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Matrix

Solution

Problem Understanding

The problem asks us to count the number of 3 x 3 magic squares inside a larger grid. A magic square is defined as a square where all numbers are distinct integers from 1 to 9 and the sum of each row, column, and the two diagonals is the same.

The input is a 2D grid of integers with dimensions row x col, where each element can range from 0 to 15. The output is a single integer representing how many 3 x 3 subgrids meet the magic square criteria.

Key points to note:

A magic square must contain numbers 1 to 9 exactly once. Any number outside this range immediately disqualifies the subgrid.
The sum for any row, column, or diagonal in a 3 x 3 magic square must equal 15, because (1+2+...+9)/3 = 15.
Edge cases include very small grids (smaller than 3x3), grids filled with numbers outside 1-9, and grids with repeated numbers.

The constraints are small: row and col are at most 10, so a brute-force approach is feasible, but there is an opportunity for minor optimization by early elimination of invalid candidates.

Approaches

The brute-force approach would iterate over every possible 3 x 3 subgrid within the row x col grid. For each subgrid, we would check whether the numbers are distinct and fall within the 1-9 range, then compute the sums of all rows, columns, and diagonals to verify the magic square property. This approach works correctly but involves repetitive sum calculations. Its time complexity is O((row-2)*(col-2) * 9) because there are (row-2)*(col-2) subgrids and 9 numbers to check per subgrid.

The optimal approach leverages the observation that a 3 x 3 magic square with numbers 1-9 always has 5 in the center. This allows us to quickly skip subgrids whose center is not 5. Further, we can use a set to ensure all numbers are distinct and within 1-9. We then check rows, columns, and diagonals for the sum 15, which is a fast constant-time check.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((row-2)(col-2) 9)	O(1)	Check every `3 x 3` subgrid thoroughly
Optimal	O((row-2)*(col-2))	O(1)	Early elimination using center=5 and set check, constant-time sum checks

Algorithm Walkthrough

Initialize a counter variable count to 0. This will store the number of magic squares found.
Iterate over each possible top-left corner (i, j) of a 3 x 3 subgrid. The loop ranges are i = 0 to row-3 and j = 0 to col-3.
For each subgrid, first check if the center element is 5. If not, skip this subgrid because no 3x3 magic square with numbers 1-9 can have a different center.
Flatten the subgrid into a list and check if all numbers are distinct and in the range 1 to 9 using a set.
Check whether each row, column, and diagonal sums to 15.
If all conditions are satisfied, increment count.
After iterating over all subgrids, return count.

Why it works: The algorithm leverages two strong invariants: the center must be 5 and the sum of rows, columns, and diagonals must be 15. By checking these conditions and uniqueness within 1-9, it guarantees that any counted subgrid is a valid magic square.

Python Solution

from typing import List

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def is_magic(i: int, j: int) -> bool:
            # Check if center is 5
            if grid[i+1][j+1] != 5:
                return False
            
            # Flatten the 3x3 subgrid and check if numbers 1-9 are all present
            nums = [grid[i+r][j+c] for r in range(3) for c in range(3)]
            if set(nums) != set(range(1, 10)):
                return False
            
            # Check rows and columns sums
            for r in range(3):
                if sum(grid[i+r][j+c] for c in range(3)) != 15:
                    return False
            for c in range(3):
                if sum(grid[i+r][j+c] for r in range(3)) != 15:
                    return False
            
            # Check diagonals
            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, cols = len(grid), len(grid[0])
        for i in range(rows - 2):
            for j in range(cols - 2):
                if is_magic(i, j):
                    count += 1
        return count

This solution first checks the center, then validates the uniqueness and sum constraints. The helper function is_magic encapsulates all the validation logic, making the main loop clean and easy to understand.

Go Solution

func numMagicSquaresInside(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    count := 0
    
    isMagic := func(i, j int) bool {
        if grid[i+1][j+1] != 5 {
            return false
        }
        seen := make(map[int]bool)
        for r := 0; r < 3; r++ {
            for c := 0; c < 3; c++ {
                val := grid[i+r][j+c]
                if val < 1 || val > 9 || seen[val] {
                    return false
                }
                seen[val] = true
            }
        }
        for r := 0; r < 3; r++ {
            sumRow := 0
            for c := 0; c < 3; c++ {
                sumRow += grid[i+r][j+c]
            }
            if sumRow != 15 {
                return false
            }
        }
        for c := 0; c < 3; c++ {
            sumCol := 0
            for r := 0; r < 3; r++ {
                sumCol += grid[i+r][j+c]
            }
            if sumCol != 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
    }
    
    for i := 0; i <= rows-3; i++ {
        for j := 0; j <= cols-3; j++ {
            if isMagic(i, j) {
                count++
            }
        }
    }
    return count
}

In Go, the logic mirrors Python, using a map to ensure distinct numbers and iterating explicitly to sum rows, columns, and diagonals. Go does not have list comprehensions, so nested loops are used.

Worked Examples

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

Iterate over top-left (0,0) subgrid:

4 3 8
9 5 1
2 7 6

Center = 5
Numbers = {1,2,3,4,5,6,7,8,9}
Row sums: 15,15,15
Column sums: 15,15,15
Diagonal sums: 15,15
Count = 1
Next subgrid (0,1):

3 8 4
5 1 9
7 6 2

Center = 1
Skip

Final answer = 1

Example 2: grid = [[8]]

Grid too small for 3x3 → 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O((row-2)*(col-2))	Each 3x3 subgrid is checked in constant time using early elimination
Space	O(1)	Only a constant amount of extra space for counting and sets/maps

Since the grid size is limited to 10x10, this solution is efficient.

Test Cases

# Provided examples
assert Solution().numMagicSquaresInside([[4,3,8,4],[9,5,1,9],[2,7,6,2]]) ==