Magic Squares In Grid — Solution in Python, Java & C++
Magic Squares In Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Magic Squares In Grid is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Google and Infosys interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Simulation
- Asked at: Amazon, Google, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A 3 × 3 magic square is a grid holding each of the digits 1 to 9 exactly once, where every row, every column and both diagonals add up to the same total.
Given a grid of integers, count how many 3 × 3 contiguous subgrids are magic squares.
Example 1
Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: The left 3 × 3 block is magic; the right one is not.
Example 2
Input: grid = [[8]]
Output: 0
Explanation: Too small to hold a 3 × 3 block.
Example 3
Input: grid = [[4,3,8],[9,5,1],[2,7,6]]
Output: 1
Constraints
row == grid.lengthcol == grid[i].length1 <= row, col <= 100 <= grid[i][j] <= 15
Hints for Magic Squares In Grid
Hint 1
There are at most
(row - 2) · (col - 2)candidate blocks, so checking each one in full is cheap.Hint 2
First reject any block that does not hold exactly the digits 1 through 9.
Hint 3
A 3 × 3 magic square always sums to 15 on every line.
How to solve Magic Squares In Grid
The grid is tiny, so try every 3 × 3 position and validate it directly. Validation is two parts: the digit set, then the eight line sums.
Approach
- For each top-left corner, mark the nine values and reject unless they are exactly
1 … 9, each once. - Check the three row sums, the three column sums and the two diagonals all equal 15.
- Count the blocks that pass.
Why it works
The total of 1 … 9 is 45, and the three rows partition the square, so if all rows are equal each must be 15 — the constant is forced, not a choice. Checking the digit set first is what makes the rest safe: without it a block of nine 5s passes every sum test.
Complexity
- Time —
O(row · col) - Space —
O(1)
Pitfalls
- Skipping the distinctness check accepts grids of all 5s.
- Both diagonals matter, not just the main one.
- Values outside
1 … 9(including 0) disqualify a block immediately.
Reference solution
Python
from typing import List
def numMagicSquaresInside(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def magic(r: int, c: int) -> bool:
vals = [grid[r + i][c + j] for i in range(3) for j in range(3)]
if sorted(vals) != [1, 2, 3, 4, 5, 6, 7, 8, 9]:
return False
for i in range(3):
if grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] != 15:
return False
if grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] != 15:
return False
if grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] != 15:
return False
if grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] != 15:
return False
return True
return sum(1 for r in range(m - 2) for c in range(n - 2) if magic(r, c))Java
public static int numMagicSquaresInside(int[][] grid) {
int m = grid.length, n = grid[0].length;
int count = 0;
for (int r = 0; r + 2 < m; r++) {
for (int c = 0; c + 2 < n; c++) if (magicAt(grid, r, c)) count++;
}
return count;
}
private static boolean magicAt(int[][] grid, int r, int c) {
boolean[] seen = new boolean[10];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int v = grid[r + i][c + j];
if (v < 1 || v > 9 || seen[v]) return false;
seen[v] = true;
}
}
for (int i = 0; i < 3; i++) {
if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] != 15) return false;
if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] != 15) return false;
}
if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] != 15) return false;
if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] != 15) return false;
return true;
}C++
static bool magicAt(vector<vector<int>>& grid, int r, int c) {
bool seen[10] = { false };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int v = grid[r + i][c + j];
if (v < 1 || v > 9 || seen[v]) return false;
seen[v] = true;
}
}
for (int i = 0; i < 3; i++) {
if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] != 15) return false;
if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] != 15) return false;
}
if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] != 15) return false;
if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] != 15) return false;
return true;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
int m = (int) grid.size(), n = (int) grid[0].size();
int count = 0;
for (int r = 0; r + 2 < m; r++) {
for (int c = 0; c + 2 < n; c++) if (magicAt(grid, r, c)) count++;
}
return count;
}JavaScript
var numMagicSquaresInside = function(grid) {
var m = grid.length, n = grid[0].length;
var magic = function(r, c) {
var seen = [];
var i, j;
for (i = 0; i <= 9; i++) seen.push(0);
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
var v = grid[r + i][c + j];
if (v < 1 || v > 9 || seen[v]) return false;
seen[v] = 1;
}
}
for (i = 0; i < 3; i++) {
if (grid[r + i][c] + grid[r + i][c + 1] + grid[r + i][c + 2] !== 15) return false;
if (grid[r][c + i] + grid[r + 1][c + i] + grid[r + 2][c + i] !== 15) return false;
}
if (grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2] !== 15) return false;
if (grid[r][c + 2] + grid[r + 1][c + 1] + grid[r + 2][c] !== 15) return false;
return true;
};
var count = 0;
for (var r = 0; r + 2 < m; r++) {
for (var c = 0; c + 2 < n; c++) if (magic(r, c)) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal