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