LeetCode Entry

840. Magic Squares In Grid

30.12.2025 medium 2025 kotlin rust

Count 'magic' 3x3 squares

840. Magic Squares In Grid medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1220

Problem TLDR

Count ‘magic’ 3x3 squares #medium

Intuition

Brute-force.

Approach

• we can enumerate each cell and translate into original matrix m[y-1][x-1] shift by y1,x1 of the magic cell

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

// 24ms
    fun numMagicSquaresInside(g: Array<IntArray>) =
        (1..<g.size-1).sumOf { y -> (1..<g[0].size-1).count { x ->
            "012345678036147258048246".map { g[y-1+(it-'0')/3][x-1+(it-'0')%3] }
            .run {toSet().size==9 && all{it in 1..9} && chunked(3).all{it.sum()== 15}}
        }}

// 0ms
    pub fn num_magic_squares_inside(g: Vec<Vec<i32>>) -> i32 {
        (1..g.len()-1).map(|y|(1..g[0].len()-1).filter(|&x|{
            let v=[0,1,2,3,4,5,6,7,8,0,3,6,1,4,7,2,5,8,0,4,8,2,4,6]
                .map(|i| g[y-1+i/3][x-1+i%3]); let mut m=0u16;
            v[..9].iter().all(|&t|0<t&&t<=9&&{m&1<<t<1&&{m|=1<<t;true}})
            && v.chunks(3).all(|c|c.iter().sum::<i32>()==15)
        }).count()as i32).sum()
    }