Difficulty: Easy | Acceptance: 54.60% | Paid: No Topics: Array, Hash Table, Matrix, Simulation
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 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.
- 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 after the game has ended.
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.
- Examples
- Constraints
- Simulation with Matrix
- Row/Column Counting
- Hash Set Tracking
Examples
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 <= rowi, coli <= 2
There are no repeated moves.
Simulation with Matrix
Intuition Simulate the game by creating a 3x3 board and placing each move alternately for players A and B, then check for winning conditions.
Steps
- Initialize a 3x3 board with empty values
- Iterate through moves, placing ‘X’ for A (even indices) and ‘O’ for B (odd indices)
- After each move, check if the current player has won by checking rows, columns, and diagonals
- If no winner after all moves, return “Draw” if board is full, otherwise “Pending”
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
board = [[0] * 3 for _ in range(3)]
def check_winner(player):
# Check rows
for i in range(3):
if all(board[i][j] == player for j in range(3)):
return True
# Check columns
for j in range(3):
if all(board[i][j] == player for i in range(3)):
return True
# Check diagonals
if all(board[i][i] == player for i in range(3)):
return True
if all(board[i][2 - i] == player for i in range(3)):
return True
return False
for i, (row, col) in enumerate(moves):
player = 1 if i % 2 == 0 else 2
board[row][col] = player
if check_winner(player):
return "A" if player == 1 else "B"
return "Draw" if len(moves) == 9 else "Pending"
Complexity
- Time: O(n) where n is the number of moves (at most 9)
- Space: O(1) for the fixed 3x3 board
- Notes: Simple and intuitive approach with constant space
Row/Column Counting
Intuition Instead of maintaining a full board, track counts for each row, column, and diagonal. A player wins when any count reaches 3.
Steps
- Initialize arrays for row counts, column counts, and variables for diagonals
- For each move, increment for player A and decrement for player B
- After each move, check if any count reaches 3 or -3
- If no winner after all moves, return “Draw” if 9 moves were made, otherwise “Pending”
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
rows = [0] * 3
cols = [0] * 3
diag1 = 0 # top-left to bottom-right
diag2 = 0 # top-right to bottom-left
for i, (row, col) in enumerate(moves):
player = 1 if i % 2 == 0 else -1
rows[row] += player
cols[col] += player
if row == col:
diag1 += player
if row + col == 2:
diag2 += player
if abs(rows[row]) == 3 or abs(cols[col]) == 3 or abs(diag1) == 3 or abs(diag2) == 3:
return "A" if player == 1 else "B"
return "Draw" if len(moves) == 9 else "Pending"
Complexity
- Time: O(n) where n is the number of moves
- Space: O(1) using fixed-size arrays
- Notes: More efficient than full board simulation, uses counting instead of checking all cells
Hash Set Tracking
Intuition Track all positions occupied by each player using sets, then check if any winning combination is fully contained in a player’s set.
Steps
- Create sets for both players A and B
- Define all 8 winning combinations (3 rows, 3 columns, 2 diagonals)
- After placing all moves, check if any winning combination is a subset of either player’s positions
- Return the winner, “Draw” if board is full, or “Pending” otherwise
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
player_a = set()
player_b = set()
# All winning combinations
win_combinations = [
# Rows
{(0, 0), (0, 1), (0, 2)},
{(1, 0), (1, 1), (1, 2)},
{(2, 0), (2, 1), (2, 2)},
# Columns
{(0, 0), (1, 0), (2, 0)},
{(0, 1), (1, 1), (2, 1)},
{(0, 2), (1, 2), (2, 2)},
# Diagonals
{(0, 0), (1, 1), (2, 2)},
{(0, 2), (1, 1), (2, 0)}
]
for i, (row, col) in enumerate(moves):
if i % 2 == 0:
player_a.add((row, col))
else:
player_b.add((row, col))
for combo in win_combinations:
if combo.issubset(player_a):
return "A"
if combo.issubset(player_b):
return "B"
return "Draw" if len(moves) == 9 else "Pending"
Complexity
- Time: O(n) where n is the number of moves
- Space: O(n) for storing player positions
- Notes: More intuitive for checking winning conditions but uses more space than counting approach