How to Solve Magic Squares In Grid

Magic Squares In Grid is a fixed-size matrix scanning problem: slide a 3x3 window, confirm the digits are exactly 1 through 9, then check that all rows, columns, and diagonals match the same sum. Because the window size never changes, each validation is constant work, so the full solution runs in O(M \cdot N) time with O(1) extra space.

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

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.

How GhostInterview Helps

• Highlights the fixed 3x3 constraint so you immediately choose window scanning instead of a heavier matrix technique.
• Points out the exact false-positive pattern in Magic Squares In Grid: matching sums without distinct digits 1 through 9.
• Keeps the solution centered on array scanning plus hash lookup, so the implementation stays short and interview-safe.

Topic Pages

• Array
• Hash Table
• Math
• Matrix

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.