1275. Find Winner on a Tic Tac Toe Game
Description
Tictactoe is played by two players A
and B
on a 3 x 3
grid. The rules of TicTacToe are:
 Players take turns placing characters into empty squares
' '
.  The first player
A
always places'X'
characters, while the second playerB
always places'O'
characters. 'X'
and'O'
characters are always placed into empty squares, never on filled ones. The game ends when there are three of the same (nonempty) character filling any row, column, or diagonal.
 The game also ends if all squares are nonempty.
 No more moves can be played if the game is over.
Given a 2D integer array moves
where moves[i] = [row_{i}, col_{i}]
indicates that the i^{th}
move will be played on grid[row_{i}][col_{i}]
. return the winner of the game if it exists (A
or B
). In case the game ends in a draw return "Draw"
. If there are still movements to play return "Pending"
.
You can assume that moves
is valid (i.e., it follows the rules of TicTacToe), the grid is initially empty, and A
will play first.
Example 1:
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] Output: "A" Explanation: A wins, they always play first.
Example 2:
Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] Output: "B" Explanation: B wins.
Example 3:
Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] Output: "Draw" Explanation: The game ends in a draw since there are no moves to make.
Constraints:
1 <= moves.length <= 9
moves[i].length == 2
0 <= row_{i}, col_{i} <= 2
 There are no repeated elements on
moves
. moves
follow the rules of tic tac toe.
Solutions
Solution 1: Determine if the last player to move can win
Since all moves
are valid, that is, there is no situation where a person continues to play after someone has won. Therefore, we only need to determine whether the last player to move can win.
We use an array cnt
of length $8$ to record the number of moves in rows, columns, and diagonals. Where $cnt[0, 1, 2]$ represent the number of moves in the $0, 1, 2$ rows respectively, and $cnt[3, 4, 5]$ represent the number of moves in the $0, 1, 2$ columns respectively. Additionally, $cnt[6]$ and $cnt[7]$ represent the number of moves on the two diagonals respectively. During the game, if a player makes $3$ moves in a row, column, or diagonal, that player wins.
If the last player to move does not win, then we determine whether the board is full. If it is full, it is a draw; otherwise, the game is not over yet.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of moves
.









