Skip to main content
Back to problems
#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)
LeetCode
solution.rs
/*
 * 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
  }
}