Problem
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 contiguous 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.
Examples
Example 1:
$$ grid = \begin{bmatrix} 4 & 3 & 8 & 4 \\ 9 & 5 & 1 & 9 \\ 2 & 7 & 6 & 2 \end{bmatrix} $$
Input: grid = [ [4,3,8,4],[9,5,1,9],[2,7,6,2] ]
Output: 1
Explanation: In total, there is only one magic square inside the given grid.
The following subgrid is a 3 x 3 magic square: $$ grid = \begin{bmatrix} 4 & 3 & 8 \\ 9 & 5 & 1 \\ 2 & 7 & 6 \end{bmatrix} $$
while this one is not: $$ grid = \begin{bmatrix} 3 & 8 & 4 \\ 5 & 1 & 9 \\ 7 & 6 & 2 \end{bmatrix} $$ Example 2:
Input: grid = [ [8] ]
Output: 0
Solution
Video Explanation
Here is the video, explaining two methods covered below.
Method 1 - Using Simple Iteration
Here is the approach we can take:
- Traverse Each Possible 3x3 Subgrid: For each possible 3x3 subgrid, extract the subgrid and check if it forms a magic square.
- Magic Square Criteria:
- A 3x3 magic square must have all distinct numbers from 1 to 9.
- The sum of each row, column, and both diagonals must be 15
Why the sum will be 15?
We know that in magic square, sum of rows will be equal…i.e. sum(row1) = sum(row2) = sum(row3). Let sum of 1 row be X. Then, sum of all rows will result in adding all the number from 1 to 9.
So, we have:
3X = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
X = 15
Steps
Here are the steps we can take:
- Traverse the grid and extract all possible 3x3 subgrids.
- For each subgrid, check if it contains all distinct numbers from 1 to 9.
- Verify if the sums of rows, columns, and diagonals are all equal to 15.
- Count the number of valid magic square subgrids.
Code
Java
public class Solution {
public int numMagicSquaresInside(int[][] grid) {
int count = 0;
int m = grid.length;
int n = grid[0].length;
// Traverse the grid to find all 3x3 subgrids
for (int i = 0; i <= m - 3; i++) {
for (int j = 0; j <= n - 3; j++) {
if (isMagicSquare(grid, i, j)) {
count++;
}
}
}
return count;
}
private boolean isMagicSquare(int[][] grid, int row, int col) {
// Check distinct numbers from 1 to 9
boolean[] seen = new boolean[10]; // indexes 1 through 9 represent numbers 1 to 9
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int num = grid[row + i][col + j];
if (num < 1 || num > 9 || seen[num]) {
return false;
}
seen[num] = true;
}
}
// Check rows
for (int i = 0; i < 3; i++) {
if (grid[row + i][col] + grid[row + i][col + 1] + grid[row + i][col + 2] != 15) {
return false;
}
if (grid[row][col + i] + grid[row + 1][col + i] + grid[row + 2][col + i] != 15) {
return false;
}
}
// diagonal
if (grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2] != 15) {
return false;
}
// off-diagonal
if (grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col] != 15) {
return false;
}
return true;
}
}
Complexity
- ⏰ Time complexity:
O(m * n)where m is number of rows and n is number of columns.- The outer loops run
O(m - 2) * (n - 2)for every possible 3x3 subgrid. - The inner checks are constant time
O(1)
- The outer loops run
- 🧺 Space complexity:
O(1)
Method 2 - Mathematics
Observation 1 - Center of Magic Square is 5
Let our magic square be:
$$ grid = \begin{bmatrix} a1 & a2 & a3 \\ a4 & a5 & a6 \\ a7 & a8 & a9 \end{bmatrix} $$
Then following sum as equations will hold, for the sums passing through a5:
a2 + a5 + a8 = 15
a4 + a5 + a6 = 15
a1 + a5 + a9 = 15
a3 + a5 + a7 = 15
If we add all the equations above, we will get:
a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + 3 * a5 = 60
sum(all_the_numbers) + 3 * a5 = 60
We saw sum of all the numbers = 45
Hence,
45 + 3 * a5 = 60
3 * a5 = 15
a5 = 5
Observation 2 - Order of other 8 numbers around middle is 43816729
Another observation for other 8 numbers is that:
- The even numbers must be in the corner,
- and the odd numbers must be on the edge.
- And it must be in a order like “43816729” （clockwise or anticlockwise)
Checkout the video explanation explaining and proving this:
So, our isMagicSquare function changes like this:
- Check the middle element is 5: O(1)
- Extract border elements: O(1) (always 8 elements)
- Check border sequence: O(1) (comparing fixed-length strings)
There are 8 patterns:
$$ \begin{bmatrix} 4 & 3 & 8 \\ 9 & 5 & 1 \\ 2 & 7 & 6 \end{bmatrix} \begin{bmatrix} 2 & 9 & 4 \\ 7 & 5 & 3 \\ 6 & 1 & 8 \end{bmatrix} \begin{bmatrix} 6 & 7 & 2 \\ 1 & 5 & 9 \\ 8 & 3 & 4 \end{bmatrix} \begin{bmatrix} 8 & 1 & 6 \\ 3 & 5 & 7 \\ 4 & 9 & 2 \end{bmatrix} $$ $$ \begin{bmatrix} 4 & 9 & 2 \\ 3 & 5 & 7 \\ 8 & 1 & 6 \end{bmatrix} \begin{bmatrix} 2 & 7 & 6 \\ 9 & 5 & 1 \\ 4 & 3 & 8 \end{bmatrix} \begin{bmatrix} 6 & 1 & 8 \\ 7 & 5 & 3 \\ 2 & 9 & 4 \end{bmatrix} \begin{bmatrix} 8 & 3 & 4 \\ 1 & 5 & 9 \\ 6 & 7 & 2 \end{bmatrix} $$
and they look like rotated strings of each other we can use Rotate String Problem. So, we will double the pattern and search current boundary pattern.
Code
Java
public class Solution {
public int numMagicSquaresInside(int[][] grid) {
int count = 0;
int m = grid.length;
int n = grid[0].length;
// Traverse the grid to find all 3x3 subgrids
for (int i = 0; i <= m - 3; i++) {
for (int j = 0; j <= n - 3; j++) {
if (isMagicSquare(grid, i, j)) {
count++;
}
}
}
return count;
}
private static final String[] MAGIC_SEQUENCES = {"4381672943816729", "4927618349276183" };
private boolean isMagicSquare(int[][] grid, int row, int col) {
if (grid[row + 1][col + 1] != 5) {
return false;
}
String border = getBorderString(grid, row, col);
for (String magicSequence: MAGIC_SEQUENCES) {
if (magicSequence.contains(border)) {
return true;
}
}
return false;
}
private String getBorderString (int[][] grid, int row, int col) {
StringBuilder sb = new StringBuilder();
int[] rowIdx = {0, 0, 0, 1, 2, 2, 2, 1};
int[] colIdx = {0, 1, 2, 2, 2, 1, 0, 0};
for (int i = 0; i < 8; i++) {
int r = row + rowIdx[i];
int c = col + colIdx[i];
sb.append(grid[r][c]);
}
return sb.toString();
}
}
Complexity
- ⏰ Time complexity:
O(m * n) - 🧺 Space complexity:
O(1)