Magic Squares In Grid
MedPrompt
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] <= 15
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through every possible 3x3 subgrid in the input grid. For each subgrid, it performs a comprehensive check to see if it satisfies all the properties of a magic square.
Algorithm
- Initialize a counter
magic_squares_countto 0. - If the grid dimensions are smaller than 3x3, return 0.
- Iterate through each row
rfrom 0 togrid.length - 3. - Inside this loop, iterate through each column
cfrom 0 togrid[0].length - 3. - For the 3x3 subgrid starting at
(r, c), call a helper functionisMagic. - The
isMagichelper function performs the following checks:- Verify that all 9 elements are distinct numbers from 1 to 9. A frequency array can be used for this.
- Calculate the sum of each of the 3 rows, 3 columns, and 2 diagonals.
- Return
trueif all 8 sums are equal to 15, otherwise returnfalse.
- If
isMagicreturnstrue, incrementmagic_squares_count. - After the loops complete, return
magic_squares_count.
Walkthrough
The algorithm iterates through the main grid with nested loops, considering each cell (r, c) as a potential top-left corner of a 3x3 subgrid. This is possible for r from 0 to rows-3 and c from 0 to cols-3.
A helper function, isMagic(grid, r, c), is called for each subgrid. This function validates two main properties:
- Distinct Numbers from 1 to 9: It checks if all 9 numbers in the subgrid are unique and fall within the required range of 1 to 9. This can be done using a frequency array or a set. If any number is out of range or duplicated, the subgrid is not magic.
- Constant Sum: It verifies that the sum of numbers in each of the three rows, three columns, and both main diagonals is equal to the magic constant, which is 15 for numbers 1-9.
A counter is maintained and incremented for every subgrid that passes all these checks.
class Solution { public int numMagicSquaresInside(int[][] grid) { int rows = grid.length; int cols = grid[0].length; if (rows < 3 || cols < 3) { return 0; } int count = 0; for (int r = 0; r <= rows - 3; r++) { for (int c = 0; c <= cols - 3; c++) { if (isMagic(grid, r, c)) { count++; } } } return count; } private boolean isMagic(int[][] grid, int r, int c) { // 1. Check for distinct numbers 1-9 int[] seen = new int[16]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { int val = grid[r + i][c + j]; if (val < 1 || val > 9 || seen[val] > 0) { return false; } seen[val]++; } } // 2. Check sums int row1 = grid[r][c] + grid[r][c+1] + grid[r][c+2]; int row2 = grid[r+1][c] + grid[r+1][c+1] + grid[r+1][c+2]; int row3 = grid[r+2][c] + grid[r+2][c+1] + grid[r+2][c+2]; int col1 = grid[r][c] + grid[r+1][c] + grid[r+2][c]; int col2 = grid[r][c+1] + grid[r+1][c+1] + grid[r+2][c+1]; int col3 = grid[r][c+2] + grid[r+1][c+2] + grid[r+2][c+2]; int diag1 = grid[r][c] + grid[r+1][c+1] + grid[r+2][c+2]; int diag2 = grid[r][c+2] + grid[r+1][c+1] + grid[r+2][c]; return row1 == 15 && row2 == 15 && row3 == 15 && col1 == 15 && col2 == 15 && col3 == 15 && diag1 == 15 && diag2 == 15; }}Complexity
Time
O(R * C), where R is the number of rows and C is the number of columns. We iterate through approximately R * C subgrids, and the check for each is a constant time operation (O(1) since it's always 3x3).
Space
O(1). The extra space used is a constant-size array for checking distinctness, which does not depend on the input grid size.
Trade-offs
Pros
Simple and direct implementation of the problem definition.
Easy to understand and verify its correctness.
Cons
Inefficient as it performs a full, expensive check on every single 3x3 subgrid.
It doesn't leverage any specific properties of magic squares for optimization.
Solutions
Solution
class Solution {private int m;private int n;private int[][] grid;public int numMagicSquaresInside(int[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans += check(i, j); } } return ans; }private int check(int i, int j) { if (i + 3 > m || j + 3 > n) { return 0; } int[] cnt = new int[16]; int[] row = new int[3]; int[] col = new int[3]; int a = 0, b = 0; for (int x = i; x < i + 3; ++x) { for (int y = j; y < j + 3; ++y) { int v = grid[x][y]; if (v < 1 || v > 9 || ++cnt[v] > 1) { return 0; } row[x - i] += v; col[y - j] += v; if (x - i == y - j) { a += v; } if (x - i + y - j == 2) { b += v; } } } if (a != b) { return 0; } for (int k = 0; k < 3; ++k) { if (row[k] != a || col[k] != a) { return 0; } } return 1; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.