840. Magic Squares In Grid

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 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

From: LeetCode
Link: 840. Magic Squares In Grid

Solution:

Ideas:

• Validates numbers are 1…9 and all distinct with seen[].

• Uses the Lo Shu property: center must be 5.

• Verifies all 8 sums (3 rows, 3 cols, 2 diagonals) equal 15.

• Time: O((rows−2)(cols−2)); constant work per window.

Code:

static bool isMagic3x3(int **g, int r, int c) {
    // All numbers must be 1..9 and distinct
    int seen[10] = {0};
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            int v = g[r + i][c + j];
            if (v < 1 || v > 9 || seen[v]) return false;
            seen[v] = 1;
        }
    }

    // Center must be 5 for a 1..9 3x3 magic square
    if (g[r + 1][c + 1] != 5) return false;

    // Every row/col/diag must sum to 15
    int s0 = g[r][c] + g[r][c + 1] + g[r][c + 2];
    if (s0 != 15) return false;

    int s1 = g[r + 1][c] + g[r + 1][c + 1] + g[r + 1][c + 2];
    int s2 = g[r + 2][c] + g[r + 2][c + 1] + g[r + 2][c + 2];
    if (s1 != 15 || s2 != 15) return false;

    int c0 = g[r][c] + g[r + 1][c] + g[r + 2][c];
    int c1 = g[r][c + 1] + g[r + 1][c + 1] + g[r + 2][c + 1];
    int c2 = g[r][c + 2] + g[r + 1][c + 2] + g[r + 2][c + 2];
    if (c0 != 15 || c1 != 15 || c2 != 15) return false;

    int d1 = g[r][c] + g[r + 1][c + 1] + g[r + 2][c + 2];
    int d2 = g[r][c + 2] + g[r + 1][c + 1] + g[r + 2][c];
    return d1 == 15 && d2 == 15;
}

int numMagicSquaresInside(int** grid, int gridSize, int* gridColSize) {
    int rows = gridSize;
    int cols = gridColSize[0];
    if (rows < 3 || cols < 3) return 0;

    int count = 0;
    for (int r = 0; r + 2 < rows; ++r) {
        for (int c = 0; c + 2 < cols; ++c) {
            if (isMagic3x3(grid, r, c)) ++count;
        }
    }
    return count;
}