Magic Squares In Grid: Subgrid Validation Explained

A magic square is a grid where every row, every column, and both diagonals all add up to the same number. LeetCode 840, Magic Squares In Grid, asks you to count how many 3x3 subgrids inside a larger grid qualify as magic squares using the digits 1 through 9. It is rated medium, and the core challenge is validating each candidate subgrid efficiently without getting lost in the bookkeeping.

The problem

You are given an m x n grid of integers. Return the number of 3x3 subgrids that form a magic square. A magic square here specifically means a 3x3 grid containing all distinct values from 1 to 9, where every row, every column, and both diagonals sum to 15.

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

The approach: sliding window validation

The idea is simple. You slide a 3x3 window across every possible position in the grid, and for each window you check whether it forms a valid magic square. Since the grid has m rows and n columns, there are (m - 2) * (n - 2) possible top-left corners for a 3x3 subgrid.

The key insight that saves you time: a 3x3 magic square using the digits 1 through 9 always has a magic constant of 15 and the center cell must be 5. You can verify this mathematically. The sum of digits 1 through 9 is 45. Three rows must share this total equally, so each row sums to 15. And because both diagonals pass through the center, the center value is forced to be 5. This gives you a fast early exit: if the center of a 3x3 window is not 5, skip it immediately.

Step-by-step walkthrough

The code

def num_magic_squares_inside(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    count = 0

    def is_magic(r: int, c: int) -> bool:
        if grid[r + 1][c + 1] != 5:
            return False

        vals = set()
        for i in range(r, r + 3):
            for j in range(c, c + 3):
                v = grid[i][j]
                if v < 1 or v > 9 or v in vals:
                    return False
                vals.add(v)

        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

    for r in range(rows - 2):
        for c in range(cols - 2):
            if is_magic(r, c):
                count += 1

    return count

The function is_magic does all the heavy lifting. It starts with the center check (must be 5), then verifies all nine values are distinct digits from 1 to 9, and finally checks all eight lines (three rows, three columns, two diagonals) for a sum of 15. The outer loop simply slides the window across every valid starting position.

Notice how the center check comes first. Since most random 3x3 subgrids will not have 5 in the center, this single comparison eliminates the majority of candidates before you do any further work.

Complexity analysis

Each subgrid check is O(1) since you always examine a fixed 3x3 grid with a constant number of sum comparisons. The outer loop visits at most (m - 2) * (n - 2) positions, making the overall time O(m * n). Space is O(1) because the set of values in each subgrid never exceeds 9 elements.

The building blocks

Fixed-size subgrid validation

The reusable pattern here is sliding a fixed-size window over a 2D grid and validating each subgrid against a set of constraints. You pick a window size (3x3 in this case), iterate over all valid top-left corners, and run your validation logic on the extracted subgrid.

for r in range(rows - k + 1):
    for c in range(cols - k + 1):
        if check_subgrid(grid, r, c, k):
            count += 1

This skeleton works for any problem where you need to examine every k x k subgrid: finding patterns, computing local statistics, or validating properties. The key is that each check runs in O(k^2) time, so the total work is O(m * n * k^2). When k is a constant (like 3 here), that simplifies to O(m * n).

You will see this same structure in problems like Valid Sudoku (checking 3x3 boxes), Game of Life (checking 3x3 neighborhoods), and any problem that asks about local properties of a matrix.

Edge cases

Before submitting, make sure your solution handles these scenarios:

• Grid too small: if the grid has fewer than 3 rows or fewer than 3 columns, there are no possible 3x3 subgrids. The loop simply does not execute, and the count stays at 0.
• Duplicate values in subgrid: values like [1, 1, 1, 2, 5, 8, 3, 7, 6] fail the distinctness check even though some sums might work out. The set-based check catches this.
• Values outside 1-9: a subgrid containing 0, 10, or any number outside the range 1 to 9 cannot be a magic square. The bounds check on each value handles this.
• All cells same value: a grid filled with 5s has the right center, but the distinctness check immediately rejects it.
• Multiple magic squares: the grid could contain more than one valid 3x3 magic square at different positions. The sliding window visits every position, so all of them get counted.

From understanding to recall

You have walked through the logic. The center-first check, the distinctness validation, the eight sum comparisons. None of these ideas are difficult on their own. But during an interview, you need to produce all of them quickly and without mistakes. Forgetting to check that values are in range, or mixing up which sums to verify, is enough to fail a problem you fully understand.

Spaced repetition helps you bridge the gap between understanding and recall. You practice writing the validation function from scratch, first today, then again in a few days, then again after a longer gap. Each time, the pattern becomes more automatic. Eventually, you see "validate a subgrid" and the structure flows out without hesitation.

The fixed-size subgrid validation pattern is one of many reusable building blocks that appear across matrix problems. Drilling these individually and reinforcing them over time is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Valid Sudoku - Grid validation with row, column, and subgrid constraints
• Spiral Matrix - Systematic traversal of a 2D matrix
• Rotate Image - In-place matrix manipulation

CodeBricks breaks Magic Squares In Grid into its subgrid validation building block, then drills it with spaced repetition. You write the center check, the distinctness test, and the sum comparisons from scratch until the pattern is automatic. When a grid validation problem shows up in your interview, you do not hesitate. You just write it.