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)