Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:
' '.A always places 'X' characters, while the second player B always places 'O' characters.'X' and 'O' characters are always placed into empty squares, never on filled ones.Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. 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 Tic-Tac-Toe), 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 <= 9moves[i].length == 20 <= rowi, coli <= 2moves.moves follow the rules of tic tac toe.In this approach, we use a 3x3 board to simulate the mechanics of a Tic Tac Toe game. For every move made, we place the respective player's symbol ('X' for player A and 'O' for player B) on the board. After each move, we check if this move results in a win for any player by verifying if there are three matching symbols in any row, column, or diagonal. If a win is found, that player is declared the winner and the game ends. If all moves are exhausted without a winner, the game is declared a draw. If there are remaining moves, the game is pending.
First, we initialize the board to be empty. We iterate through the given moves, alternately placing 'X' and 'O' based on the current player. After placing a move, we check all possible win conditions (rows, columns, diagonals) to see if the last move resulted in a win. If no winner is found, we check if all moves have been placed to determine if the game is a draw or if it's still pending.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the moves. In the worst case, it checks 8 winning conditions for all 9 moves.
Space Complexity: O(1), since the board is of fixed size (3x3).
Instead of simulating the grid itself, this approach tracks the status of each row, column, and the two diagonals using counters. Each player will have their counters, incrementing or decrementing upon making a move. The first instance a counter reaches 3 or -3 indicates a player has won the game. This method significantly reduces the need to check the grid extensively for each move while still adhering to the rules of Tic Tac Toe.
This solution uses integer counters to track the influence of moves on the board. Each player's move updates these counters; the goal is to detect a completion of three moves in any direction (horizontally, vertically, or diagonally). This approach efficiently determines the winner without maintaining the entire board's state.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of moves.
Space Complexity: O(1), as only fixed-size counters are involved.
| Approach | Complexity |
|---|---|
| Simulation with a 3x3 Board | Time Complexity: O(n), where n is the length of the moves. In the worst case, it checks 8 winning conditions for all 9 moves. |
| Row and Column Count | Time Complexity: O(n), where n is the number of moves. |
Tic-tac-toe Best win #hack ever. You’re welcome. #win 🔥😈🔥knots and crosses • PaperBatMan • 297,437 views views
Watch 9 more video solutions →Practice Find Winner on a Tic Tac Toe Game with our built-in code editor and test cases.
Practice on FleetCode