08 Apr 2024•TypeScript•Medium

Magic Squares in Grid

Check every 3×3 window for the 1..9 magic square pattern using center and parity pruning.

Magic squares of size 3 have a strict structure: the center must be 5, each row, column, and diagonal sums to 15, and the digits 1 through 9 appear exactly once. I iterate each 3×3 sub-grid and apply those checks in order of cheapest to most expensive.

The early rejection on the center cell eliminates about 80% of windows up front. A simple frequency map handles the uniqueness constraint before I bother computing row or column sums.

Checklist

Center cell is 5.
All values are between 1 and 9 inclusive.
Each value appears exactly once.
Every row, column, and diagonal totals 15 (precomputed row sums make this quick).

Complexity

For an m×n grid there are (m - 2)(n - 2) windows. Each validation is constant work on nine cells, so the whole algorithm is O(mn) time and O(1) additional space.

Solution files

TypeScript•magic-squares-in-grid/solution.ts

function numMagicSquaresInside(grid: number[][]): number {
  const rows = grid.length;
  const cols = rows ? grid[class="syntax-number">0].length : class="syntax-number">0;
  if (rows < class="syntax-number">3 || cols < class="syntax-number">3) {
    return class="syntax-number">0;
  }

  let count = class="syntax-number">0;

  for (let r = class="syntax-number">0; r <= rows - class="syntax-number">3; ++r) {
    for (let c = class="syntax-number">0; c <= cols - class="syntax-number">3; ++c) {
      if (isMagic(grid, r, c)) {
        count += class="syntax-number">1;
      }
    }
  }

  return count;
}

function isMagic(grid: number[][], r: number, c: number): boolean {
  if (grid[r + class="syntax-number">1][c + class="syntax-number">1] !== class="syntax-number">5) {
    return false;
  }

  const seen = new Array<boolean>(class="syntax-number">10).fill(false);
  for (let i = class="syntax-number">0; i < class="syntax-number">3; ++i) {
    for (let j = class="syntax-number">0; j < class="syntax-number">3; ++j) {
      const value = grid[r + i][c + j];
      if (value < class="syntax-number">1 || value > class="syntax-number">9 || seen[value]) {
        return false;
      }
      seen[value] = true;
    }
  }

  const rows = [
    grid[r][c] + grid[r][c + class="syntax-number">1] + grid[r][c + class="syntax-number">2],
    grid[r + class="syntax-number">1][c] + grid[r + class="syntax-number">1][c + class="syntax-number">1] + grid[r + class="syntax-number">1][c + class="syntax-number">2],
    grid[r + class="syntax-number">2][c] + grid[r + class="syntax-number">2][c + class="syntax-number">1] + grid[r + class="syntax-number">2][c + class="syntax-number">2],
  ];

  const cols = [
    grid[r][c] + grid[r + class="syntax-number">1][c] + grid[r + class="syntax-number">2][c],
    grid[r][c + class="syntax-number">1] + grid[r + class="syntax-number">1][c + class="syntax-number">1] + grid[r + class="syntax-number">2][c + class="syntax-number">1],
    grid[r][c + class="syntax-number">2] + grid[r + class="syntax-number">1][c + class="syntax-number">2] + grid[r + class="syntax-number">2][c + class="syntax-number">2],
  ];

  const diagonals = [
    grid[r][c] + grid[r + class="syntax-number">1][c + class="syntax-number">1] + grid[r + class="syntax-number">2][c + class="syntax-number">2],
    grid[r][c + class="syntax-number">2] + grid[r + class="syntax-number">1][c + class="syntax-number">1] + grid[r + class="syntax-number">2][c],
  ];

  for (const sum of [...rows, ...cols, ...diagonals]) {
    if (sum !== class="syntax-number">15) {
      return false;
    }
  }

  return true;
}

export { numMagicSquaresInside };