Magic Squares In Grid — Medium Problem & Solution

Problem statement

A 3 × 3 magic square is a grid holding each of the digits 1 to 9 exactly once, where every row, every column and both diagonals add up to the same total.

Given a grid of integers, count how many 3 × 3 contiguous subgrids are magic squares.

Example 1

Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: The left 3 × 3 block is magic; the right one is not.

Example 2

Input: grid = [[8]]
Output: 0
Explanation: Too small to hold a 3 × 3 block.

Example 3

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

Constraints

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15

How to solve Magic Squares In Grid

The grid is tiny, so try every 3 × 3 position and validate it directly. Validation is two parts: the digit set, then the eight line sums.

Approach

1. For each top-left corner, mark the nine values and reject unless they are exactly 1 … 9, each once.
2. Check the three row sums, the three column sums and the two diagonals all equal 15.
3. Count the blocks that pass.

Why it works

The total of 1 … 9 is 45, and the three rows partition the square, so if all rows are equal each must be 15 — the constant is forced, not a choice. Checking the digit set first is what makes the rest safe: without it a block of nine 5s passes every sum test.

Complexity

• Time — O(row · col)
• Space — O(1)

Pitfalls

• Skipping the distinctness check accepts grids of all 5s.
• Both diagonals matter, not just the main one.
• Values outside 1 … 9 (including 0) disqualify a block immediately.

Reference solution

Python

from typing import List

def numMagicSquaresInside(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])

    def magic(r: int, c: int) -> bool:
        vals = [grid[r + i][c + j] for i in range(3) for j in range(3)]
        if sorted(vals) != [1, 2, 3, 4, 5, 6, 7, 8, 9]:
            return False
        for i in range(3):
            if grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] != 15:
                return False
            if grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] != 15:
                return False
        if grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] != 15:
            return False
        if grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] != 15:
            return False
        return True

    return sum(1 for r in range(m - 2) for c in range(n - 2) if magic(r, c))

JavaScript

var numMagicSquaresInside = function(grid) {
    var m = grid.length, n = grid[0].length;
    var magic = function(r, c) {
        var seen = [];
        var i, j;
        for (i = 0; i <= 9; i++) seen.push(0);
        for (i = 0; i < 3; i++) {
            for (j = 0; j < 3; j++) {
                var v = grid[r + i][c + j];
                if (v < 1 || v > 9 || seen[v]) return false;
                seen[v] = 1;
            }
        }
        for (i = 0; i < 3; i++) {
            if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] !== 15) return false;
            if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] !== 15) return false;
        }
        if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] !== 15) return false;
        if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] !== 15) return false;
        return true;
    };
    var count = 0;
    for (var r = 0; r + 2 < m; r++) {
        for (var c = 0; c + 2 < n; c++) if (magic(r, c)) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium