Find Winner on a Tic Tac Toe Game - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You receive a list of moves for a 3x3 Tic Tac Toe game played by two players, A and B. Each move contains a row and column. After applying the moves in order, determine whether player A wins, player B wins, the game is a draw, or the game is still pending.
Approach 1: Simulation with a 3x3 Board (O(n) time, O(1) space)
Create a 3x3 board and simulate the game exactly as it would be played. Iterate through the moves array and place either 'A' or 'B' depending on whose turn it is. After filling the board, check all rows, columns, and the two diagonals for three identical marks. Since the board size is fixed (3x3), the win check is constant work. This approach is easy to reason about and mirrors the real game logic, making it a good starting point when working with matrix simulations.
Approach 2: Row and Column Count (O(n) time, O(1) space)
Instead of maintaining the full board, track counts for each row, column, and both diagonals. Player A adds +1 to the counters and player B adds -1. For every move, update rows[r], cols[c], and the diagonal counters if applicable. If any counter reaches 3 or -3, one player has filled that line and wins immediately. This technique avoids scanning the board and works well for problems involving incremental state updates using array counters and lightweight simulation.
Recommended for interviews: The row and column counting method is the preferred solution. It processes each move once and detects a win instantly without scanning the board. The board simulation approach demonstrates clear understanding of the game rules, but the counter technique shows stronger problem‑solving skills and awareness of constant-space optimizations.
Approach 1: Simulation with a 3x3 Board
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.
Complexity
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).
Approach 2: Row and Column Count
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.
Complexity
Time Complexity: O(n), where n is the number of moves.
Space Complexity: O(1), as only fixed-size counters are involved.
Approach 3: Determine if the last player to move can win
Since all moves are valid, that is, there is no situation where a person continues to play after someone has won. Therefore, we only need to determine whether the last player to move can win.
We use an array cnt of length 8 to record the number of moves in rows, columns, and diagonals. Where cnt[0, 1, 2] represent the number of moves in the 0, 1, 2 rows respectively, and cnt[3, 4, 5] represent the number of moves in the 0, 1, 2 columns respectively. Additionally, cnt[6] and cnt[7] represent the number of moves on the two diagonals respectively. During the game, if a player makes 3 moves in a row, column, or diagonal, that player wins.
If the last player to move does not win, then we determine whether the board is full. If it is full, it is a draw; otherwise, the game is not over yet.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of moves.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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. |
| Determine if the last player to move can win | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation with 3x3 Board | O(n) | O(1) | Best when you want straightforward logic that mirrors the actual game board |
| Row and Column Count | O(n) | O(1) | Optimal approach when you want constant-time win detection without scanning the board |
Video Solution
Leetcode - Find Winner on a Tic Tac Toe Game (Python) • Timothy H Chang • 9,444 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Winner on a Tic Tac Toe Game easy or hard?
Find Winner on a Tic Tac Toe Game Python/Java solution
How to solve Find Winner on a Tic Tac Toe Game in O(n)?
What is the best approach for Find Winner on a Tic Tac Toe Game?
Is Find Winner on a Tic Tac Toe Game asked at Google/Amazon/Meta?
What data structure is used in Find Winner on a Tic Tac Toe Game?
What is the time complexity of Find Winner on a Tic Tac Toe Game?
Ready to solve this problem?
Practice Find Winner on a Tic Tac Toe Game with our built-in code editor and test cases.
Practice on FleetCode