// Runtime: 1 ms, faster than 44.95% of Java online submissions for Magic Squares In Grid.
// Memory Usage: 34.6 MB, less than 100.00% of Java online submissions for Magic Squares In Grid.
class Solution {
    public int numMagicSquaresInside(int[][] grid) {
        int size = 3;

        int maxNumber = size * size;

        int magicSum = 0;
        for (int i = 1; i <= maxNumber; i++) magicSum += i;
        magicSum /= size;


        int[][][] directions = buildDirections(size);

        int count = 0;
        for (int i = 0; i <= grid.length - size; i++)
            for (int j = 0; j <= grid[0].length - size; j++)
                if (isMagic(grid, i, j, size, maxNumber, magicSum, directions)) count++;

        return count;
    }

    private boolean isMagic(int[][] grid, int i, int j, int size, int maxNumber, int magicSum, int[][][] directions) {
        boolean[] presence = new boolean[maxNumber];

        for (int ii = i; ii < i + size; ii++)
            for (int jj = j; jj < j + size; jj++) {
                int n = grid[ii][jj];
                if (n < 1 || n > maxNumber) {
                    return false;
                }
                if (presence[n - 1]) return false;
                else presence[n - 1] = true;
            }

        for (int[][] direction: directions) {
            if (sum(grid, i, j, direction) != magicSum) return false;
        }

        return true;
    }

    private int[][][] buildDirections(int size) {
        int[][][] directions = new int[2*size + 2][][];
        int pos = 0;

        for (int r = 0; r < size; r++) {
            int[][] direction = new int[size][2];
            for (int c = 0; c < size; c++) direction[c] = new int[] { r, c };
            directions[pos++] = direction;
        }

        for (int c = 0; c < size; c++) {
            int[][] direction = new int[size][2];
            for (int r = 0; r < size; r++) direction[r] = new int[] { r, c };
            directions[pos++] = direction;
        }

        int[][] d1 = new int[size][2];
        for (int i = 0; i < size; i++) d1[i] = new int[] { i, i };
        directions[pos++] = d1;

        int[][] d2 = new int[size][2];
        for (int i = 0; i < size; i++) d2[i] = new int[] { size - i - 1, i };
        directions[pos++] = d2;

        return directions;
    }

    private int sum(int[][] grid, int i, int j, int[][] direction) {
        int sum = 0;
        for (int[] delta: direction) sum += grid[i + delta[0]][j + delta[1]];
        return sum;
    }
}