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.
We can use an array of length n times 2 + 2 to record the number of pieces each player has in each row, each column, and the two diagonals. We need two such arrays to record the number of pieces for the two players respectively.
When a player has n pieces in a certain row, column, or diagonal, that player wins.
In terms of time complexity, the time complexity of each move is O(1). The space complexity is O(n), where n is the length of the side of the chessboard.
Python
Java
C++
Go
TypeScript
| 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 |
Design Tic-Tac-Toe (Leetcode premium) • Fraz • 16,621 views views
Watch 9 more video solutions →Practice Design Tic-Tac-Toe with our built-in code editor and test cases.
Practice on FleetCode