Watch 10 video solutions for Design Tic-Tac-Toe, a medium level problem involving Array, Hash Table, Design. This walkthrough by Gaurav Sen has 288,970 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Assume the following rules are for the tic-tac-toe game on an n x n board between two players:
n of their marks in a horizontal, vertical, or diagonal row wins the game.Implement the TicTacToe class:
TicTacToe(int n) Initializes the object the size of the board n.int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Return
0 if there is no winner after the move,1 if player 1 is the winner after the move, or2 if player 2 is the winner after the move.
Example 1:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1] Explanation TicTacToe ticTacToe = new TicTacToe(3); Assume that player 1 is "X" and player 2 is "O" in the board. ticTacToe.move(0, 0, 1); // return 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | ticTacToe.move(0, 2, 2); // return 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | ticTacToe.move(2, 2, 1); // return 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| ticTacToe.move(1, 1, 2); // return 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| ticTacToe.move(2, 0, 1); // return 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| ticTacToe.move(1, 0, 2); // return 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|
Constraints:
2 <= n <= 1001 or 2.0 <= row, col < n(row, col) are unique for each different call to move.n2 calls will be made to move.
Follow-up: Could you do better than O(n2) per move() operation?
Problem Overview: Design a Tic-Tac-Toe class that supports a move(row, col, player) operation and returns the winner if one exists. The board size is n x n, and after each move you must determine whether the current player has completed a row, column, or diagonal.
Approach 1: Board Simulation with Line Scan (O(n) time, O(n²) space)
Store the entire board using a 2D array from the matrix category. After each move, place the player's mark and scan the corresponding row, column, and possibly the two diagonals to check whether every cell belongs to the same player. Each check requires iterating through up to n cells, giving O(n) time per move. Space complexity is O(n²) because the full board must be stored. This approach mirrors how the game works conceptually but wastes time repeatedly scanning lines.
Approach 2: Row and Column Counting (O(1) time, O(n) space)
Instead of storing the full board, track counts for each row and column using arrays. Maintain rows[n], cols[n], and two variables for the main and anti-diagonal. Player 1 adds +1 to these counters while Player 2 adds -1. After updating the relevant counters, check whether any counter reaches n or -n. That indicates a complete line for a player. Each move performs constant updates and checks, so the time complexity is O(1). Space complexity is O(n). This technique relies on simple arithmetic aggregation rather than repeatedly scanning the board.
The counting approach fits naturally with problems involving incremental updates and state tracking, a common pattern in design problems. The counters behave like lightweight accumulators instead of a full game board.
Approach 3: Hash-Based Line Tracking (O(1) time, O(n) space)
A variation stores row and column counters in a hash table keyed by index. Each move updates the row key, column key, and diagonal keys if applicable. When any counter reaches n or -n, a winner is found. This approach offers the same O(1) time per move but is typically less efficient than arrays due to hashing overhead. It becomes useful when the board size or line identifiers are dynamic.
Recommended for interviews: Interviewers expect the counting approach with row, column, and diagonal accumulators. The brute-force scan demonstrates the baseline understanding of the game rules, but the counter technique shows that you recognize redundant work and reduce each move to constant-time updates.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Board Simulation with Line Scan | O(n) per move | O(n²) | Simple implementation when performance is not critical |
| Row/Column Counting Arrays | O(1) per move | O(n) | Optimal solution for interviews and large boards |
| Hash Map Line Tracking | O(1) average | O(n) | Useful when indices or board dimensions are dynamic |