Find Winner on a Tic Tac Toe Game — Problem & Solution
Find Winner on a Tic Tac Toe Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Winner on a Tic Tac Toe Game is an easy coding problem on arrays, hash table and matrix, asked in Amazon, Microsoft and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Matrix, Simulation
- Asked at: Amazon, Microsoft, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two players take turns on a 3 × 3 grid. A always moves first and places X; B places O. moves[i] = [row, col] is the cell claimed on the i-th turn, and no cell is claimed twice.
Return "A" or "B" if that player has three in a row (horizontally, vertically or diagonally), "Draw" if all nine cells are filled with no winner, and "Pending" if the game is unfinished.
Example 1
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: A
Explanation: A holds the main diagonal.
Example 2
Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: B
Explanation: B holds the anti-diagonal.
Example 3
Input: moves = [[0,0],[1,1]]
Output: Pending
Constraints
1 <= moves.length <= 9moves[i].length == 20 <= moves[i][j] <= 2No cell is claimed twice.
Hints for Find Winner on a Tic Tac Toe Game
Hint 1
Replay the moves onto a 3 × 3 board — even moves belong to A, odd moves to B.
Hint 2
Then check the eight lines: three rows, three columns and two diagonals.
Hint 3
Only after finding no winner does the move count decide between Draw and Pending.
How to solve Find Winner on a Tic Tac Toe Game
Replay the moves onto a 3 × 3 board (even turns are A), then test the eight winning lines; only if none wins does the move count decide Draw versus Pending.
Approach
- Fill
board[r][c]with 1 for A's moves and 2 for B's. - For each of the 3 rows, 3 columns and 2 diagonals, check for three equal non-zero cells.
- Return the winner, else
"Draw"if 9 moves were played, else"Pending".
Why it works
A finished line is the only win condition, and since moves alternate with A first, the parity of the move index identifies the player.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Check for a winner before declaring a draw — a game can be won on the ninth move.
Reference solution
Python
def tictactoe(moves) -> str:
board = [[0] * 3 for _ in range(3)]
for i, (r, c) in enumerate(moves):
board[r][c] = 1 if i % 2 == 0 else 2
lines = [
[(0, 0), (0, 1), (0, 2)], [(1, 0), (1, 1), (1, 2)], [(2, 0), (2, 1), (2, 2)],
[(0, 0), (1, 0), (2, 0)], [(0, 1), (1, 1), (2, 1)], [(0, 2), (1, 2), (2, 2)],
[(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)],
]
for line in lines:
a, b, c = line
v = board[a[0]][a[1]]
if v != 0 and v == board[b[0]][b[1]] and v == board[c[0]][c[1]]:
return "A" if v == 1 else "B"
return "Draw" if len(moves) == 9 else "Pending"Java
public static String tictactoe(int[][] moves) {
int[][] board = new int[3][3];
for (int k = 0; k < moves.length; k++) {
board[moves[k][0]][moves[k][1]] = k % 2 == 0 ? 1 : 2;
}
int[][][] lines = {
{{0, 0}, {0, 1}, {0, 2}}, {{1, 0}, {1, 1}, {1, 2}}, {{2, 0}, {2, 1}, {2, 2}},
{{0, 0}, {1, 0}, {2, 0}}, {{0, 1}, {1, 1}, {2, 1}}, {{0, 2}, {1, 2}, {2, 2}},
{{0, 0}, {1, 1}, {2, 2}}, {{0, 2}, {1, 1}, {2, 0}}
};
for (int[][] line : lines) {
int v = board[line[0][0]][line[0][1]];
if (v != 0 && v == board[line[1][0]][line[1][1]] && v == board[line[2][0]][line[2][1]]) {
return v == 1 ? "A" : "B";
}
}
return moves.length == 9 ? "Draw" : "Pending";
}C++
string tictactoe(vector<vector<int>>& moves) {
int board[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
for (int k = 0; k < (int) moves.size(); k++) {
board[moves[k][0]][moves[k][1]] = k % 2 == 0 ? 1 : 2;
}
int lines[8][3][2] = {
{{0, 0}, {0, 1}, {0, 2}}, {{1, 0}, {1, 1}, {1, 2}}, {{2, 0}, {2, 1}, {2, 2}},
{{0, 0}, {1, 0}, {2, 0}}, {{0, 1}, {1, 1}, {2, 1}}, {{0, 2}, {1, 2}, {2, 2}},
{{0, 0}, {1, 1}, {2, 2}}, {{0, 2}, {1, 1}, {2, 0}}
};
for (int i = 0; i < 8; i++) {
int v = board[lines[i][0][0]][lines[i][0][1]];
if (v != 0 && v == board[lines[i][1][0]][lines[i][1][1]] && v == board[lines[i][2][0]][lines[i][2][1]]) {
return v == 1 ? "A" : "B";
}
}
return moves.size() == 9 ? "Draw" : "Pending";
}JavaScript
var tictactoe = function(moves) {
const board = [];
for (let r = 0; r < 3; r++) board.push(new Array(3).fill(0));
for (let i = 0; i < moves.length; i++) {
board[moves[i][0]][moves[i][1]] = i % 2 === 0 ? 1 : 2;
}
const lines = [
[[0, 0], [0, 1], [0, 2]], [[1, 0], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]],
[[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 1], [2, 1]], [[0, 2], [1, 2], [2, 2]],
[[0, 0], [1, 1], [2, 2]], [[0, 2], [1, 1], [2, 0]]
];
for (let i = 0; i < lines.length; i++) {
const line = lines[i];
const v = board[line[0][0]][line[0][1]];
if (v !== 0 && v === board[line[1][0]][line[1][1]] && v === board[line[2][0]][line[2][1]]) {
return v === 1 ? "A" : "B";
}
}
return moves.length === 9 ? "Draw" : "Pending";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets