Find Winner on a Tic Tac Toe Game
EasyPrompt
Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:
- Players take turns placing characters into empty squares
' '. - The first player
Aalways places'X'characters, while the second playerBalways 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 (non-empty) character filling any row, column, or diagonal.
- The game also ends if all squares are non-empty.
- No more moves can be played if the game is over.
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 <= 2- There are no repeated elements on
moves. movesfollow the rules of tic tac toe.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the game by creating a 3x3 grid and placing the moves of players A and B according to the input. After all given moves are placed on the grid, it performs a check of all 8 possible winning lines (3 rows, 3 columns, and 2 diagonals) to determine if a player has won. If no winner is found, it checks if the board is full to declare a draw or if the game is still pending.
Algorithm
- Initialize a 3x3
chararraygridto represent the game board. - Iterate through the
movesarray. For each move at indexi:- If
iis even, it's Player A's turn. Place 'X' atgrid[moves[i][0]][moves[i][1]]. - If
iis odd, it's Player B's turn. Place 'O' atgrid[moves[i][0]][moves[i][1]].
- If
- After populating the grid, create a helper function
isWinner(grid, player)to check for a win. - Inside
isWinner, check all 8 winning lines (3 rows, 3 columns, 2 diagonals) for the specifiedplayercharacter. - Call
isWinner(grid, 'X'). If it returns true, the winner is "A". - Call
isWinner(grid, 'O'). If it returns true, the winner is "B". - If no winner is found, check if the number of moves is 9. If so, the game is a "Draw".
- Otherwise, the game is still in progress, so the result is "Pending".
Walkthrough
First, we initialize a 3x3 character array grid to represent the Tic-Tac-Toe board. We then iterate through the moves array. For each move, we determine the current player based on the index of the move. Player A makes moves at even indices (0, 2, 4, ...) and places 'X', while Player B makes moves at odd indices (1, 3, 5, ...) and places 'O'. We update the grid with the corresponding character at the specified [row, col].
After populating the grid with all the moves, we check for a winner. We can write a helper function that takes the grid and a player's character ('X' or 'O') and returns true if that player has won. This function checks all 3 rows, 3 columns, and 2 diagonals. If it finds any line completely filled with the player's character, it confirms a win.
We first check if player A has won. If so, we return "A". Then we check for player B. If B has won, we return "B". If neither player has won, we check the total number of moves. If moves.length is 9, the board is full, and the game is a "Draw". Otherwise, there are still empty squares and no winner, so the game is "Pending".
class Solution { public String tictactoe(int[][] moves) { char[][] grid = new char[3][3]; for (int i = 0; i < moves.length; i++) { int r = moves[i][0]; int c = moves[i][1]; if (i % 2 == 0) { grid[r][c] = 'X'; // Player A } else { grid[r][c] = 'O'; // Player B } } if (isWinner(grid, 'X')) { return "A"; } if (isWinner(grid, 'O')) { return "B"; } if (moves.length == 9) { return "Draw"; } else { return "Pending"; } } private boolean isWinner(char[][] grid, char player) { // Check rows for (int i = 0; i < 3; i++) { if (grid[i][0] == player && grid[i][1] == player && grid[i][2] == player) { return true; } } // Check columns for (int i = 0; i < 3; i++) { if (grid[0][i] == player && grid[1][i] == player && grid[2][i] == player) { return true; } } // Check diagonals if (grid[0][0] == player && grid[1][1] == player && grid[2][2] == player) { return true; } if (grid[0][2] == player && grid[1][1] == player && grid[2][0] == player) { return true; } return false; }}Complexity
Time
O(1), because the number of moves is at most 9 and the grid size is fixed at 3x3. The loops for populating and checking the grid run a constant number of times.
Space
O(1), as we use a fixed-size 3x3 grid, which does not depend on the number of moves.
Trade-offs
Pros
The logic is very straightforward and easy to follow, as it mimics the actual gameplay.
Simple to implement and debug.
Cons
It processes all moves before checking for a winner, even if a win occurred earlier in the game.
Slightly more memory usage due to the 3x3 grid compared to just using counters.
Solutions
Solution
class Solution {public String tictactoe(int[][] moves) { int n = moves.length; int[] cnt = new int[8]; for (int k = n - 1; k >= 0; k -= 2) { int i = moves[k][0], j = moves[k][1]; cnt[i]++; cnt[j + 3]++; if (i == j) { cnt[6]++; } if (i + j == 2) { cnt[7]++; } if (cnt[i] == 3 || cnt[j + 3] == 3 || cnt[6] == 3 || cnt[7] == 3) { return k % 2 == 0 ? "A" : "B"; } } return n == 9 ? "Draw" : "Pending"; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.