A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.
Given a row x col grid of integers, how many 3 x 3 magic square subgrids are there?
Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.
Example 1:
Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]] Output: 1 Explanation: 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
Constraints:
row == grid.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15Problem Overview: You are given a matrix and must count how many 3x3 subgrids form a magic square. A valid magic square contains the digits 1-9 exactly once, and every row, column, and both diagonals sum to the same value (15 for a 3x3 grid).
Approach 1: Brute Force and Check Conditions (O(m*n) time, O(1) space)
Scan every possible 3x3 subgrid using two nested loops. For each starting position (i, j), extract the nine values and validate the magic square conditions. First verify that all digits are between 1 and 9 and appear exactly once using a small boolean array or hash table. Then compute the sums of all three rows, three columns, and the two diagonals. If all sums match (15), the subgrid is valid.
This approach works because the grid size checked each time is fixed (3x3). Even though multiple checks are performed, they are constant operations. The algorithm iterates across the grid once, giving overall O(m*n) time with constant extra space.
Approach 2: Pattern Matching Optimization (O(m*n) time, O(1) space)
A key property of every 3x3 magic square using digits 1-9 is that the center must always be 5. Additionally, the corners and edges follow specific rotation patterns such as 4,9,2,7,6,1,8,3. Instead of computing every sum, you first check whether the center cell equals 5. If not, the subgrid cannot be a magic square.
Next, read the outer ring of the 3x3 grid and compare it against known cyclic patterns representing valid magic squares and their rotations. This avoids repeated row/column calculations and quickly filters invalid candidates. The algorithm still scans all possible positions in the matrix, so the time complexity remains O(m*n), but the constant work per check is smaller.
This pattern-based validation relies on mathematical properties of magic squares, making it a clever application of math and symmetry recognition.
Recommended for interviews: Start with the brute force validation approach. It clearly demonstrates your understanding of magic square rules and grid traversal. After that, mention the pattern insight (center equals 5 and cyclic edge patterns). Interviewers value candidates who first implement the straightforward solution and then recognize the mathematical optimization.
This approach involves iterating through each possible 3x3 subgrid within the larger grid. For each subgrid, we check if it is a magic square by validating the sum of each row, each column, and both diagonals to see if they all equal 15. Additionally, check if the subgrid contains all distinct numbers between 1 and 9. This straightforward method works well given the constraint where the largest grid size is 10x10.
This Python function first checks if the numbers in the 3x3 subgrid are exactly those between 1 and 9. If they are, it further checks if the sums of all rows, columns, and diagonals are equal to 15. The main function iterates over all possible subgrids within the main grid and counts how many are magic squares.
Time complexity: O(n*m), where n and m are the number of rows and columns, respectively, since we check each 3x3 subgrid.
Space complexity: O(1), no extra space is required other than a few variables.
This approach leverages the fact that any 3x3 magic square with numbers from 1 to 9 must have specific sums for rows, columns, and diagonals. By using pattern matching, we can check if the middle element is always 5 (since the sum of 1 to 9 is 45, and any 3 rows, columns, or diagonals equate to the central element being crucial with 15/3 = 5). This limits the checks needed and optimizes the process.
This JavaScript solution checks each subgrid for being a magic square by checking preconditioned constants like the center must be 5 and the sum of borders equating to 15. By reducing unnecessary checks, efficiency is enhanced.
JavaScript
Java
Time complexity: O(n*m), since each subgrid must be checked.
Space complexity: O(1), since memory use is constant beyond some numeric vectors.
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.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Brute Force and Check Conditions | Time complexity: O(n*m), where n and m are the number of rows and columns, respectively, since we check each 3x3 subgrid. |
| Using Pattern Matching | Time complexity: O(n*m), since each subgrid must be checked. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force and Check Conditions | O(m*n) | O(1) | Best general approach. Easy to implement and clearly validates all magic square rules. |
| Pattern Matching Optimization | O(m*n) | O(1) | When you know the mathematical properties of 3x3 magic squares and want fewer checks per subgrid. |
Magic Squares In Grid - Leetcode 840 - Python • NeetCodeIO • 15,289 views views
Watch 9 more video solutions →Practice Magic Squares In Grid with our built-in code editor and test cases.
Practice on FleetCode