Magic Squares In Grid

Magic Squares In Grid

What is this problem about?

The Magic Squares In Grid interview question gives you a grid of integers. Your goal is to count how many $3 \times 3$ contiguous subgrids constitute a "magic square". A magic square is a $3 \times 3$ grid filled with distinct numbers from exactly 1 to 9, where every row, every column, and both diagonals all sum up to the exact same number (which happens to be 15).

Why is this asked in interviews?

This is a matrix parsing and validation problem. Interviewers ask it to test your attention to detail and your ability to write clean, modular validation functions. It evaluates whether you can handle dense lists of constraints (distinct 1-9, specific dimension, multiple sum checks) without writing a massive, unreadable block of spaghetti code.

Algorithmic pattern used

This utilizes the Sliding Window / Subgrid Search pattern combined with Math / Validation Helper Functions. Since the size of the magic square is fixed at $3 \times 3$, you simply iterate through all possible top-left corners of a $3 \times 3$ grid within the larger matrix. For each possible $3 \times 3$ subgrid, you pass it to a helper function that rigorously checks the 1-9 distinct property and the row/col/diagonal sums.

Example explanation

If you are given a grid, you iterate row from 0 to rows - 3 and col from 0 to cols - 3. For a specific $3 \times 3$ subgrid at (row, col):

1. Verify it contains exactly digits 1 through 9. (An array of size 10 can tally occurrences).
2. Check if the three rows sum to 15.
3. Check if the three columns sum to 15.
4. Check if the two diagonals sum to 15. An interesting mathematical property of a $3 \times 3$ magic square using digits 1-9 is that the absolute center cell must be 5. You can use if (grid[row+1][col+1] != 5) return false; as an instant $O(1)$ filter before doing the heavy sum calculations!

Common mistakes candidates make

The most prevalent mistake is forgetting to verify that the numbers are strictly between 1 and 9 and are completely distinct. If a grid contains 5 in every single cell, the rows and columns will all sum to 15, but it is NOT a valid magic square. Candidates often only check the sums and fail the test cases containing duplicate numbers or numbers like 0 or 10.

Interview preparation tip

When tackling the Magic Squares In Grid coding problem, isolate the validation logic. Do not write the sum checks inside your main double-for loop. Create a private boolean isMagicSquare(grid, r, c) method. Mentioning the "center must be 5" trick to the interviewer will earn you massive bonus points, as it shows strong analytical and mathematical deduction skills alongside your coding ability.