Magic Squares In Grid
MediumArrayHash TableMathMatrix
Solution
export function numMagicSquaresInside(grid: number[][]): number {
const [row, col] = [grid.length, grid[0].length];
let answer = 0;
for (let y = 0; y < row - 2; y++) {
for (let x = 0; x < col - 2; x++) {
if (isMagicSquare(grid, y, x)) {
answer += 1;
}
}
}
return answer;
}
function isMagicSquare(grid: number[][], startY: number, startX: number) {
return hasDistinctNumber(grid, startY, startX) && hasSameSum(grid, startY, startX);
}
function hasDistinctNumber(grid: number[][], startY: number, startX: number) {
const set = new Set<number>();
for (let y = startY; y < startY + 3; y++) {
for (let x = startX; x < startX + 3; x++) {
if (grid[y][x] < 1 || 9 < grid[y][x] || set.has(grid[y][x])) {
return false;
}
set.add(grid[y][x]);
}
}
return true;
}
function hasSameSum(grid: number[][], startY: number, startX: number) {
const deltas = [
[1, 0],
[0, 1],
[1, 1],
[1, -1],
];
const positions = [
[0, 0, 0],
[0, 1, 0],
[0, 2, 0],
[0, 0, 1],
[1, 0, 1],
[2, 0, 1],
[0, 0, 2],
[0, 2, 3],
];
const set = new Set<number>();
for (const [y, x, d] of positions) {
const [dy, dx] = deltas[d];
let sum = 0;
let [cy, cx] = [startY + y, startX + x];
for (let i = 0; i < 3; i++) {
sum += grid[cy][cx];
[cy, cx] = [cy + dy, cx + dx];
}
set.add(sum);
}
return set.size === 1;
}
Complexity
- Time:
O(N^2)
- Space:
O(1)