#840

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Magic Squares In Grid

Scan every 3x3 window, reject invalid digits fast, then verify row, column, and diagonal sums for Magic Squares In Grid.

array hash table math matrix

Problem Statement

In LeetCode 840, you are given a matrix and must count how many 3x3 subgrids form a valid magic square. For this problem, a valid 3x3 magic square uses each number from 1 to 9 exactly once, and every row, every column, and both diagonals add to the same total.

The key detail is that the input grid itself is not limited to 1 through 9; values can be as large as 15, so many 3x3 windows fail before any sum check matters. That makes this an array scanning problem where each candidate window is filtered by digit range and uniqueness before the final magic-square verification.

Examples

Example 1

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

Output: 1

The following subgrid is a 3 x 3 magic square:

while this one is not:

In total, there is only one magic square inside the given grid.

Example 2

Input: grid = [[8]]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Scan each possible 3x3 subgrid

Iterate the top-left corner of every 3x3 window in the matrix. Since Magic Squares In Grid only ever checks 3x3 candidates, you do not need dynamic programming or prefix sums; you just enumerate all valid starting positions and validate each fixed-size block.

Reject impossible windows with digit and uniqueness checks

For the current 3x3 window, verify that all nine values are between 1 and 9 and appear exactly once. A small boolean array or bitmask works well here. This step prevents false positives where row sums happen to match even though the subgrid contains duplicates or values like 10 through 15.

Verify the magic-square sums

Once the digits are confirmed, compare the sums of the three rows, three columns, and two diagonals. In a valid 3x3 magic square built from 1 through 9, these totals must all match. Because the window is constant size, this verification is O(1), which keeps the overall scan at O(M \cdot N).

Complexity Analysis

Metric	Value
Time	O(M \cdot N)
Space	O(1)

There are (M - 2) \cdot (N - 2) possible 3x3 windows, and each one takes constant time to inspect because it always contains exactly nine cells. That gives O(M \cdot N) time overall. Extra space stays O(1) because the hash lookup structure for digits never grows beyond the fixed 1-to-9 range.

What Interviewers Usually Probe

They want you to notice the 3x3 size is fixed, so a brute-force window scan is already optimal enough.
They expect an early rejection step for digits outside 1 to 9 or repeated numbers before doing all sum checks.
They may be testing whether you avoid overengineering a constant-size matrix problem with unnecessary preprocessing.

Common Pitfalls or Variants

Common pitfalls

Checking only equal row and column sums can misclassify windows that reuse digits or include values above 9.
Forgetting to validate both diagonals misses the classic failure case where rows and columns look consistent but the square is not magic.
Building a general n x n magic-square framework wastes time here because LeetCode 840 only asks for fixed 3x3 windows.

Follow-up variants

Return the coordinates of each magic square instead of just the count.
Change the task to detect almost-magic 3x3 windows where exactly one line sum is wrong.
Generalize the validator so it checks a provided k x k subgrid, which removes the constant-time advantage of this problem.

FAQ

What is the core pattern in Magic Squares In Grid?

The core pattern is array scanning plus hash lookup. You slide a 3x3 window across the grid, use a tiny lookup structure to confirm the digits are exactly 1 through 9, and then check the eight required line sums.

Why is the center value often useful in this problem?

In any 3x3 magic square using 1 through 9, the center must be 5. Some optimized solutions use that as an extra early filter, but it is optional because the full digit and sum validation is already constant time.

Why is the time complexity O(M \cdot N) instead of O(M \cdot N \cdot 9)?

The extra factor is absorbed into the constant because every candidate window always has exactly nine cells. In interview terms, Magic Squares In Grid is linear in the number of possible 3x3 starting positions.

Do I need a hash set if the values are only 1 through 15?

You need some constant-size uniqueness check, but it does not have to be a full hash set. A boolean array of size 10 or a bitmask is usually cleaner and faster for rejecting duplicates and out-of-range digits.

What is the most common wrong approach for LeetCode 840?

The most common mistake is checking only whether row, column, and diagonal sums match. That misses invalid windows with duplicate numbers or digits outside 1 through 9, which this problem explicitly allows in the input grid.

terminal

Solution

Solution 1: Enumeration

We directly enumerate the top-left coordinates $(i, j)$ of each $3 \times 3$ submatrix, then check whether the submatrix satisfies the "magic square" property. If so, we increment the answer by one. After the enumeration, we return the answer.

class Solution:
    def numMagicSquaresInside(self, grid: List[List[int]]) -> int:
        def check(i: int, j: int) -> int:
            if i + 3 > m or j + 3 > n:
                return 0
            s = set()
            row = [0] * 3
            col = [0] * 3
            a = b = 0
            for x in range(i, i + 3):
                for y in range(j, j + 3):
                    v = grid[x][y]
                    if v < 1 or v > 9:
                        return 0
                    s.add(v)
                    row[x - i] += v
                    col[y - j] += v
                    if x - i == y - j:
                        a += v
                    if x - i == 2 - (y - j):
                        b += v
            if len(s) != 9 or a != b:
                return 0
            if any(x != a for x in row) or any(x != a for x in col):
                return 0
            return 1

        m, n = len(grid), len(grid[0])
        return sum(check(i, j) for i in range(m) for j in range(n))

Continue Practicing

#781 rabbits in forest #939 minimum area rectangle #957 prison cells after n days