Find Winner on a Tic Tac Toe Game - Video Solutions
Leetcode - Find Winner on a Tic Tac Toe Game (Python)
Find Winner on a Tic Tac Toe Game - Video Solution
Watch 10 video solutions for Find Winner on a Tic Tac Toe Game, a easy level problem involving Array, Hash Table, Matrix. This walkthrough by Timothy H Chang has 9,444 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |