Watch 10 video solutions for Magic Squares In Grid, a medium level problem involving Array, Hash Table, Math. This walkthrough by NeetCodeIO has 15,289 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |