840. Magic Squares In Grid

Brute-force

class Solution {
public:
    int numMagicSquaresInside(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        int res = 0;
        for (int i = 0; i < m - 2; i++)
        {
            for (int j = 0; j < n - 2; j++)
            {
                if (isMagicSqures(grid, i, j)) res++;
            }
        }
        return res;
    }

    bool isMagicSqures(vector<vector<int>>& grid, int r, int c)
    {
        vector<bool> seen(10);
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                int num = grid[r + i][c + j];
                if (num < 1 || num > 9) return false;
                if (seen[num]) return false;
                seen[num] = true;
            }
        }

        int postiveDiag = grid[r + 2][c] + grid[r + 1][c + 1] + grid[r][c + 2];
        int negativeDiag = grid[r][c] + grid[r + 1][c + 1] + grid[r + 2][c + 2];

        if (postiveDiag != negativeDiag) return false;

        int r1 = grid[r][c] + grid[r + 1][c] + grid[r + 2][c];
        int r2 = grid[r][c + 1] + grid[r + 1][c + 1] + grid[r + 2][c + 1];
        int r3 = grid[r][c + 2] + grid[r + 1][c + 2] + grid[r + 2][c + 2];

        if (r1 != postiveDiag || r2 != postiveDiag || r3 != postiveDiag) return false;

        int c1 = grid[r][c] + grid[r][c + 1] + grid[r][c + 2];
        int c2 = grid[r + 1][c] + grid[r + 1][c + 1] + grid[r + 1][c + 2];
        int c3 = grid[r + 2][c] + grid[r + 2][c + 1] + grid[r + 2][c + 2];

        if (c1 != postiveDiag || c2 != postiveDiag || c3 != postiveDiag) return false;

        return true;
    }
};

• T: $O(M \cdot N)$
• S: $O(1)$