LeetCode Entry
840. Magic Squares In Grid
Count 9x9 1..9 equal row col diag sum subgrids
840. Magic Squares In Grid medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/697
Problem TLDR
Count 9x9 1..9 equal row col diag sum subgrids #medium
Intuition
Digits must be distinct 1, 2, 3, 4, 5, 6, 7, 8, 9, and all of them must be present.
Approach
Let’s just do a brute-force search
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(1)\)
Code
fun numMagicSquaresInside(grid: Array<IntArray>): Int {
var res = 0; val r = -1..1
for (y in 1..<grid.lastIndex) for (x in 1..<grid[0].lastIndex) {
if ((0..<9).map { grid[y + it / 3 - 1][x + it % 3 - 1] }
.filter { it in 1..9 }.toSet().size < 9) continue
if (setOf(r.sumOf { grid[y - 1][x + it] },
r.sumOf { grid[y][x + it] },
r.sumOf { grid[y + 1][x + it] },
r.sumOf { grid[y + it][x - 1] },
r.sumOf { grid[y + it][x] },
r.sumOf { grid[y + it][x + 1] },
r.sumOf { grid[y + it][x + it] },
r.sumOf { grid[y + it][x - it] }).size == 1) res++
}
return res
}
pub fn num_magic_squares_inside(grid: Vec<Vec<i32>>) -> i32 {
let mut res = 0;
for y in 1..grid.len() - 1 { for x in 1..grid[0].len() - 1 {
let nums = (0..9).map(|i| grid[y + i / 3 - 1][x + i % 3 - 1])
.filter(|&x| 0 < x && x < 10).collect::<HashSet<_>>();
if nums.len() < 9 { continue }
let sums = vec![
(0..3).map(|i| grid[y + i - 1][x - 1]).sum(),
(0..3).map(|i| grid[y + i - 1][x]).sum(),
(0..3).map(|i| grid[y + i - 1][x + 1]).sum(),
(0..3).map(|i| grid[y - 1][x + i - 1]).sum(),
(0..3).map(|i| grid[y][x + i - 1]).sum(),
(0..3).map(|i| grid[y + 1][x + i - 1]).sum(),
(0..3).map(|i| grid[y + i - 1][x + i - 1]).sum(),
(0..3).map(|i| grid[y + i - 1][x - i + 1]).sum::<i32>(),
];
if sums.iter().collect::<HashSet<_>>().len() == 1 { res += 1 }
}}; res
}