348. Design Tic-Tac-Toe
Asked at Databricks
Difficulty
Medium
Time
O(1) per move
Space
O(n)
Pattern
Array
Companies
1
Problem
Design a class that plays tic-tac-toe on an n x n board. Two players take turns. Player 1 and player 2 each place their own mark on an empty cell.
You must implement two methods. The constructor TicTacToe(n) sets the board size. The method move(row, col, player) places the mark of player at cell (row, col). Every move is guaranteed to be legal: the cell is empty, and the game has not been won yet.
After each move, return 0 if nobody has won, 1 if player 1 just completed a full row, column or diagonal, or 2 if player 2 did. A player wins by filling all n cells of one row, one column, the main diagonal (top-left to bottom-right), or the anti-diagonal (top-right to bottom-left).
The follow-up asks you to do better than scanning the whole board after each move, which would cost O(n^2) per move.
A win is one full line
Constraints
- ●
2 <= n <= 100 - ●
player is 1 or 2 - ●
0 <= row, col < n - ●
(row, col) is unique for each different call to move - ●
At most n^2 calls will be made to move
Examples
["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]][null, 0, 0, 0, 0, 0, 0, 1]["TicTacToe", "move", "move", "move", "move", "move"]
[[2], [0, 0, 1], [0, 1, 2], [1, 0, 1], [1, 1, 2]][null, 0, 0, 0, 2]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
How to Think About It
Brute force: after every move, scan the entire board checking all rows, columns, and diagonals. Time per move is O(n^2) for an n x n board.
Track the count of pieces per row, per column, and for both diagonals for each player. A player wins when any of their counts reaches n.
Use two arrays of size n for rows, two for columns, and two scalar variables for diagonals. One player adds +1, the other adds -1.
After placing a mark, check if the corresponding row, column, or diagonal count has absolute value n. If so, that player wins.
The anti-diagonal index for cell (r, c) in an n x n board is r + c == n - 1. Track it separately from the main diagonal where r == c.
Example on 3x3: Player 1 places at (0,0), (1,1), (2,2). Row counts: [1,1,1]. Col counts: [1,1,1]. Main diag count: 3. Winner detected at third move.
Optimal Approach
Step 1: Maintain arrays rows[n] and cols[n] initialized to zero, plus diag and antiDiag scalars.
Step 2: On move (row, col) by player p, add +1 if player 1 or -1 if player 2 to rows[row], cols[col], and the relevant diagonal(s).
Step 3: After updating, check if any of rows[row], cols[col], diag, or antiDiag has absolute value n. If so, return the player number.
Step 4: If no win condition is met, return 0.
Step 5: Example walkthrough on 3x3: Player 1 at (0,0) -> rows=[1,0,0], cols=[1,0,0], diag=1. Player 2 at (0,1) -> rows=[0,0,0], cols=[1,-1,0], diag=1. Player 1 at (1,1) -> rows=[0,1,0], cols=[1,-1,1], diag=2. Player 2 at (0,2) -> rows=[0,0,0], cols=[1,-1,0], diag=2, antiDiag=0. Player 1 at (2,2) -> diag=3, absolute value equals n, player 1 wins.
Time: O(1) per move. Space: O(n) for the row and column arrays.
Count per line instead of scanning
What Trips People Up in Real Interviews
Scanning the whole board after each move instead of using counters. That gives O(n^2) per move instead of O(1).
Forgetting that a row, column, or diagonal is only a win if it is entirely filled by one player, not just partially occupied.
Mixing up which player increments vs decrements the counters. Establish the convention early and stick to it.
Not handling the anti-diagonal correctly. Remember the condition is r + c == n - 1, not r + c == n.
Trying to use a HashSet of positions per player and then scanning all combinations, which is unnecessary overhead.
Solution Code
O(1) per move timeclass TicTacToe:
def __init__(self, n: int):
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.diag = 0
self.anti_diag = 0
def move(self, row: int, col: int, player: int) -> int:
val = 1 if player == 1 else -1
self.rows[row] += val
self.cols[col] += val
if row == col:
self.diag += val
if row + col == self.n - 1:
self.anti_diag += val
if (abs(self.rows[row]) == self.n or
abs(self.cols[col]) == self.n or
abs(self.diag) == self.n or
abs(self.anti_diag) == self.n):
return player
return 0Frequently Asked Questions
What is the Design Tic-Tac-Toe problem?
Design a Tic-Tac-Toe game that supports the player moves and determines the winner after each move in constant time.
How do you solve Design Tic-Tac-Toe?
The optimal approach runs in O(1) per move time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Design Tic-Tac-Toe?
Design Tic-Tac-Toe is asked at Databricks. It is a medium difficulty problem.
What are common mistakes on Design Tic-Tac-Toe?
- Scanning the whole board after each move instead of using counters. That gives `O(n^2)` per move instead of `O(1)`.
- Forgetting that a row, column, or diagonal is only a win if it is entirely filled by one player, not just partially occupied.
- Mixing up which player increments vs decrements the counters. Establish the convention early and stick to it.
- Not handling the anti-diagonal correctly. Remember the condition is `r + c == n - 1`, not `r + c == n`.
- Trying to use a HashSet of positions per player and then scanning all combinations, which is unnecessary overhead.