Abstract / Summary

Find how many 3x3 subgrids in a given grid have equal sums across each row, column, and both diagonals.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Math
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method numMagicSquaresInside. The method receives a two-dimensional list grid and returns the count of 3 × 3 sub-grids that satisfy the definition of a magic square using the numbers 1 through 9 exactly once. The algorithm proceeds by iterating over every possible top-left coordinate of a 3 × 3 window, invoking a helper predicate to verify the magic-square property, and accumulating the total.

Core Logic

Dimension Extraction

width  = len(grid[0])
height = len(grid)

The code extracts the horizontal and vertical extents of the input matrix once, avoiding repeated length calculations inside the nested loops.

Magic-Square Predicate

The nested function ismagic(x, y) encapsulates all checks required for a candidate sub-grid whose top-left corner is at column x and row y.

Distinct-Number Verification

unique = set()
for j in range(3):
    for i in range(3):
        unique.add(grid[y + j][x + i])
if len(unique) != 9:
    return False
if min(unique) != 1:
    return False
if max(unique) != 9:
    return False

A set collects the nine values; the size test guarantees all entries are different. The subsequent min and max checks enforce that the values span exactly the range 1-9, which is a necessary condition for a 3 × 3 magic square using those digits.

Row, Column, and Diagonal Sums

h1 = grid[y    ][x    ] + grid[y    ][x + 1] + grid[y    ][x + 2]
h2 = grid[y + 1][x    ] + grid[y + 1][x + 1] + grid[y + 1][x + 2]
h3 = grid[y + 2][x    ] + grid[y + 2][x + 1] + grid[y + 2][x + 2]
v1 = grid[y    ][x    ] + grid[y + 1][x    ] + grid[y + 2][x    ]
v2 = grid[y    ][x + 1] + grid[y + 1][x + 1] + grid[y + 2][x + 1]
v3 = grid[y    ][x + 2] + grid[y + 1][x + 2] + grid[y + 2][x + 2]
d1 = grid[y    ][x    ] + grid[y + 1][x + 1] + grid[y + 2][x + 2]
d2 = grid[y    ][x + 2] + grid[y + 1][x + 1] + grid[y + 2][x    ]
return h1 == h2 and h2 == h3 and h3 == v1 and v1 == v2 and v2 == v3 and v3 == d1 and d1 == d2

The code computes the sum of each of the three rows (h1, h2, h3), three columns (v1, v2, v3), and the two diagonals (d1, d2). The final boolean expression ensures that all eight sums are equal, which is the defining property of a magic square.

Scanning the Grid

result = 0
for y in range(height - 2):
    for x in range(width - 2):
        if ismagic(x, y):
            result += 1
return result

The outer loops iterate only over positions where a full 3 × 3 window fits, i.e., up to height-2 rows and width-2 columns. For each candidate, the predicate is called; a true result increments the counter.

Edge Cases Handled

The implementation explicitly guards against several subtle conditions:

• Grids that are smaller than 3 × 3 are implicitly handled because the range limits (height-2, width-2) become empty, resulting in a zero count without additional checks.
• Sub-grids containing duplicate numbers are rejected by the len(unique) != 9 test.
• Sub-grids that include numbers outside the 1-9 range are filtered out by the min and max comparisons. This prevents false positives where the distinctness condition holds but the values are not the required set.
• The sum checks automatically reject any arrangement where rows, columns, or diagonals do not share the same total, covering cases such as rotated or reflected magic squares that still meet the numeric constraints.

Performance Optimizations

The code incorporates several practical optimizations that reduce unnecessary work:

• Single Pass Dimension Retrieval - Width and height are computed once before the loops, avoiding repeated attribute access.
• Early Rejection via Set Checks - By building the set of nine values first, the function can exit immediately when the distinctness or range conditions fail, bypassing the more expensive sum calculations for invalid candidates.
• Compact Loop Bounds - The iteration limits are calculated as height - 2 and width - 2, ensuring that the inner body never attempts to index outside the matrix, thus eliminating the need for boundary checks inside ismagic.
• Local Variable Access - All references to grid, x, and y are captured from the enclosing scope, allowing the Python interpreter to resolve them quickly without repeated attribute lookups.
• Straightforward Arithmetic - Row, column, and diagonal sums are expressed as direct additions of three elements each, avoiding function calls or list comprehensions that would add overhead.

These choices collectively keep the runtime proportional to the number of possible 3 × 3 windows, with constant-time work per window after the early exit checks.

Conclusion

The solution presents a clear, self-contained approach to counting magic squares within a matrix. It isolates the validation logic in a helper function, leverages set operations for distinctness, and performs explicit sum comparisons to enforce the magic-square property. The design handles edge conditions such as insufficient grid size and out-of-range values gracefully, while the early-exit strategy and tight loop bounds contribute to an efficient execution profile.

Think of this code like playing a game of hide and seek with a special set of building blocks. Imagine there is a big tray filled with numbers arranged in a grid. The goal is to walk across the grid and look at every little three-by-three square hidden inside it.

When the code finds one of these small squares, it acts like a detective to see if it is a magic square. First, it looks at the numbers inside the box to make sure they are all different and that every number from one to nine is present. If even one number is missing or repeated, the detective knows it is not magic and moves on.

If the numbers are all correct, the detective starts adding them up. It adds the numbers in every row, every column, and even the two diagonal lines that cross through the middle. For a square to be truly magic, every single one of those sums must be the exact same number. If the row across the top equals the same as the column down the side and the diagonal line, then that square is a winner. The code keeps track of how many of these magic squares it finds, counting them up one by one until it has checked every corner of the tray.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java			Python			TS
	WalkCCC	C++	Java			Python
	leetcode.ca	C++	Java		Rust	Python	JS	Go	TS
	LeetcodeHelp	C++	Java			Python
	Progiez	C++	Java			Python
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai		Java
	fsq	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lkwq007					Python
	lzl124631x	C++
	ruoru				Rust
	suxrobGM			C#
	varunu28		Java
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
withaarzoo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality