Skip to main content
Talentd

Design Tic-Tac-Toe - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableDesignMatrix9 min readAsked at: Amazon, Microsoft, Apple +10
Practice this problem

Problem Statement

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves are allowed.
  3. A player who succeeds in placing 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, or
    • 2 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 <= 100
  • player is 1 or 2.
  • 0 <= row, col < n
  • (row, col) are unique for each different call to move.
  • At most n2 calls will be made to move.

 

Follow-up: Could you do better than O(n2) per move() operation?

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Board Simulation with Line ScanO(n) per moveO(n²)Simple implementation when performance is not critical
Row/Column Counting ArraysO(1) per moveO(n)Optimal solution for interviews and large boards
Hash Map Line TrackingO(1) averageO(n)Useful when indices or board dimensions are dynamic

Video Solution

Design Tic-Tac-Toe (Leetcode premium) • Fraz • 16,743 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Tic-Tac-Toe easy or hard?
Design Tic-Tac-Toe is generally rated Medium difficulty. The straightforward board simulation is easy to implement, but the optimal O(1) solution requires recognizing that line counts can be tracked incrementally instead of rescanning the board.
Design Tic-Tac-Toe Python/Java solution
In Python or Java, the typical solution stores integer arrays for rows and columns and two variables for diagonals. Each move updates the relevant counters using +1 or -1 depending on the player and checks if the absolute value reaches n to determine the winner.
How to solve Design Tic-Tac-Toe in O(1)?
Maintain arrays for row and column counts plus two variables for diagonals. Player 1 increments counters while Player 2 decrements them. After each update, check whether any counter equals n or -n. That condition indicates a winning line and keeps each move constant time.
What is the best approach for Design Tic-Tac-Toe?
The best approach uses counting arrays for rows, columns, and diagonals. Each move updates the relevant counters and checks whether the absolute value reaches n, which means a player completed a line. This reduces the operation to O(1) time per move with O(n) space, making it optimal for interviews.
Is Design Tic-Tac-Toe asked at Google/Amazon/Meta?
Design Tic-Tac-Toe appears in interviews that evaluate system design thinking for simple games and state management. Variations of this problem have been reported in interviews at companies like Google, Amazon, and Meta, especially for junior and mid-level roles.
What data structure is used in Design Tic-Tac-Toe?
The optimal implementation uses arrays to track row and column counts along with two variables for diagonals. Some variations use hash maps, but arrays are faster and simpler because the board size is known.
What is the time complexity of Design Tic-Tac-Toe?
The optimal solution runs in O(1) time per move using row, column, and diagonal counters. A brute-force simulation that scans the board requires O(n) time per move because it must check up to n cells in a row or column.

Ready to solve this problem?

Practice Design Tic-Tac-Toe with our built-in code editor and test cases.

Practice on FleetCode
Previous

Valid Tic-Tac-Toe State