840. Magic Squares In Grid

Description

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 a row x col grid of integers, how many 3 x 3 contiguous magic square subgrids are there?

Note: while a magic square can only contain numbers from 1 to 9, grid may contain numbers up to 15.

 

Example 1:

Input: grid = [[4,3,8,4],[9,5,1,9],[2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:

while this one is not:

In total, there is only one magic square inside the given grid.

Example 2:

Input: grid = [[8]]
Output: 0

 

Constraints:

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 10
• 0 <= grid[i][j] <= 15

 

Solutions

Solution: Math

• Time complexity: O(n²)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
const numMagicSquaresInside = function (grid) {
  const n = grid.length;
  const m = grid[0].length;
  let result = 0;

  const isMagicSquare = (row, col) => {
    const upperLeft = grid[row - 1][col - 1];
    const upper = grid[row - 1][col];
    const upperRight = grid[row - 1][col + 1];
    const left = grid[row][col - 1];
    const current = grid[row][col];
    const right = grid[row][col + 1];
    const lowerLeft = grid[row + 1][col - 1];
    const lower = grid[row + 1][col];
    const lowerRight = grid[row + 1][col + 1];
    const nums = new Set([upperLeft, upper, upperRight, left, current, right, lowerLeft, lower, lowerRight]);

    if (nums.size !== 9) return false;

    for (const num of nums) {
      if (num > 9 || num < 1) return false;
    }
    if (upperLeft + upper + upperRight !== 15) return false;
    if (lowerLeft + lower + lowerRight !== 15) return false;
    if (upperLeft + left + lowerLeft !== 15) return false;
    if (upper + current + lower !== 15) return false;
    if (upperRight + right + lowerRight !== 15) return false;
    if (upperLeft + current + lowerRight !== 15) return false;
    if (upperRight + current + lowerLeft !== 15) return false;
    return true;
  };

  for (let row = 1; row < n - 1; row++) {
    for (let col = 1; col < m - 1; col++) {
      if (grid[row][col] !== 5) continue;
      if (isMagicSquare(row, col)) result += 1;
    }
  }
  return result;
};