Design Tic-Tac-Toe

Design a Tic-Tac-Toe game where player can make moves. After each move, return the winning player (1 or 2) or 0 if no winner yet.

Example 1

TicTacToe(3), move(0,0,1)→0, move(0,2,2)→0, move(2,2,1)→0, move(1,1,2)→0, move(2,0,1)→0, move(1,0,2)→0, move(2,1,1)→1

Solution Approach

Track row sums, column sums, and diagonal sums for each player. A player wins when any sum reaches n in absolute value.

rows[2][n], cols[2][n], diag[2], antiDiag[2].
On move(r,c,player): update row[p][r], col[p][c], diag[p] if r==c, antiDiag[p] if r+c==n-1.
If any reaches n: return player.

Java

class TicTacToe {
    int[][] rows, cols;
    int[] diag, anti;
    int n;

    public TicTacToe(int n) {
        this.n=n; rows=new int[2][n]; cols=new int[2][n]; diag=new int[2]; anti=new int[2];
    }
    public int move(int row, int col, int player) {
        int p = player-1;
        rows[p][row]++; cols[p][col]++;
        if (row==col) diag[p]++;
        if (row+col==n-1) anti[p]++;
        if (rows[p][row]==n||cols[p][col]==n||diag[p]==n||anti[p]==n) return player;
        return 0;
    }
}

Time Complexity: move: O(1)
Space Complexity: O(N)