Find Winner on a Tic Tac Toe Game
Easy · Matrix · Array · Hash Table · Matrix · Simulation
Problem
Two players, A and B, play tic-tac-toe on a 3 x 3 board. A always moves first and places X; B places O. Players alternate, a move always goes into an empty square, and the game stops as soon as someone owns a full row, column or diagonal, or when all nine squares are filled.
You are given moves, where moves[i] = [row, col] is the square chosen on turn i. The sequence is guaranteed to be a legal game. Return "A" or "B" if that player has won, "Draw" if the board is full with no winner, or "Pending" if the game is still in progress.
Examples
Input: moves = [[1,1],[0,0],[2,0],[0,2],[0,1],[2,2],[2,1]] Output: "A"
A holds (1,1), (2,0), (0,1) and (2,1); (0,1), (1,1) and (2,1) are the middle column.
Input: moves = [[0,0],[1,1],[2,2],[0,2],[2,0],[1,0],[2,1]] Output: "A"
A completes the bottom row (2,0), (2,1), (2,2) on the seventh move.
Input: moves = [[1,1],[0,0],[0,1]] Output: "Pending"
Only three squares are taken and nobody has a line yet.
Constraints
- 1 <= len(moves) <= 9
- len(moves[i]) == 2
- 0 <= row, col <= 2
- All moves are distinct and follow the rules of the game.
Approaches
- Baseline: fill the board, check every line — time O(m + 8 · 3), space O(9)
Follow-up
On a 3 × 3 board both solutions are instant. On an n × n board the counters still update in O(1) per move while rescanning lines costs O(n), which is the point of the "first winning move on an n × n board" use case. The other use case runs the rules backwards: can a given position occur in a legal game at all?
Related problems
Start free on Cariara · Coding problems · System design studio
