#840
Medium Algorithms Magic squares in grid
Array Hash Table Math Matrix
55.1% acceptance
Feb 22, 2026
1105
1901
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.
Solution
Rust
Time O(n²)
Space O(n)
/*
* 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.length
* col == grid[i].length
* 1 <= row, col <= 10
* 0 <= grid[i][j] <= 15
*/
impl Solution {
pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
let rows = grid.len();
let cols = grid[0].len();
if rows < 3 || cols < 3 { return 0; }
let mut count = 0;
for r in 0..rows-2 {
for c in 0..cols-2 {
if Self::is_magic(&grid, r, c) { count += 1; }
}
}
count
}
fn is_magic(grid: &Vec<Vec<i32>>, r: usize, c: usize) -> bool {
let mut seen = [false; 10];
for i in 0..3 {
for j in 0..3 {
let v = grid[r+i][c+j];
if v < 1 || v > 9 || seen[v as usize] { return false; }
seen[v as usize] = true;
}
}
let g = |i: usize, j: usize| grid[r+i][c+j];
let s = 15;
(0..3).all(|i| g(i,0)+g(i,1)+g(i,2)==s) &&
(0..3).all(|j| g(0,j)+g(1,j)+g(2,j)==s) &&
g(0,0)+g(1,1)+g(2,2)==s &&
g(0,2)+g(1,1)+g(2,0)==s
}
}