Question:

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example:

  1. Input: [[4,3,8,4],
  2.         [9,5,1,9],
  3.         [2,7,6,2]]
  4. Output: 1
  5. Explanation: 
  6. The following subgrid is a 3 x 3 magic square:
  7. 438
  8. 951
  9. 276
  11. while this one is not:
  12. 384
  13. 519
  14. 762
  16. In total, there is only one magic square inside the given grid.

Solution:

  1. /**
  2.  * @param {number[][]} grid
  3.  * @return {number}
  4.  */
  5. var numMagicSquaresInside = function(grid) {
  6.     if (!grid || grid.length < 3 || grid[0].length < 3) return 0;
  8.     let row = grid.length;
  9.     let col = grid[0].length;
  10.     let count = 0;
  12.     for (let r = 1; r < row - 1; r++) {
  13.         for (let c = 1; c < col - 1; c++) {
  14.             if (grid[r][c] === 5) {
  16.                 if (!validSurroundNum(grid,r,c)) continue;
  18.                 if (grid[r-1][c-1] + grid[r+1][c+1] !== 10) continue; // left top, right bottom = 10
  19.                 if (grid[r+1][c-1] + grid[r-1][c+1] !== 10) continue; // left bottom, right top =10
  21.                 if (grid[r-1][c-1] + grid[r-1][c] + grid[r-1][c+1] !== 15) continue; // top row = 15
  22.                 if (grid[r+1][c-1] + grid[r+1][c] + grid[r+1][c+1] !== 15) continue; // bottom row = 15
  24.                 if (grid[r-1][c-1] + grid[r][c-1] + grid[r+1][c-1] !== 15) continue; // left col = 15
  25.                 if (grid[r-1][c+1] + grid[r][c+1] + grid[r+1][c+1] !== 15) continue; // right col = 15
  27.                 count += 1;
  28.             }
  29.         }
  30.     }
  31.     return count;
  32. };
  34. function validSurroundNum(grid, x,y) {
  35.     let set = new Set();
  36.     for (let i = -1; i < 1; i++) {
  37.         for (let j = -1; j < 1; j++) {
  38.             if (set.has(grid[x+i][y+j]) || grid[x+i][y+j] < 1 || grid[x+i][y+j] > 9) {
  39.                 return false;   
  40.             } else {
  41.                 set.add(grid[x+i][y+j]);
  42.             }
  43.         }
  44.     }
  45.     return true;
  46. }

Runtime: 52 ms, faster than 100.00% of JavaScript online submissions for Magic Squares In Grid.