Design Tic-Tac-Toe
Design Tic-Tac-Toe is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (signed line counters), runs in O(1) per move time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (store the board, check the lines through the move) up.
Problem
Design a TicTacToe class for an n x n board shared by two players, numbered 1 and 2. The first player to fill an entire row, an entire column, or one of the two main diagonals with their own marks wins.
TicTacToe(int n)creates an empty board of sizen.int move(int row, int col, int player)placesplayer’s mark on the empty cell(row, col)and returnsplayerif this move wins the game, or0if nobody has won yet.
Moves are always legal: the cell is empty and the game has not been won yet. Can you make every move faster than O(n²)?
Examples
Example 1
- Input
TicTacToe(3), move(1, 1, 1), move(0, 2, 2), move(0, 0, 1), move(2, 0, 2), move(2, 2, 1)- Output
0, 0, 0, 0, 1- Why
- Player 1 holds (0,0), (1,1) and (2,2), the full main diagonal, on the fifth move.
Example 2
- Input
TicTacToe(2), move(0, 1, 2), move(1, 1, 1), move(0, 0, 2)- Output
0, 0, 2- Why
- On a 2 x 2 board, player 2 fills the whole top row with two marks.
Constraints
2 <= n <= 100playeris 1 or 2.0 <= row, col < n, and every move goes to an empty cell.- No move is made after a player has won.
- At most
n^2calls tomove.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (store the board, check the lines through the move) | O(n) per move | O(n²) |
| Optimal (signed line counters) | O(1) per move | O(n) |
1Brute force (store the board, check the lines through the move)
O(n) per moveAt most four lines of length n are scanned after each move.O(n²)The whole board is stored.Keep the full n x n grid. After placing a mark, walk the row, the column and, if the cell is on one, each diagonal, and see whether all n cells belong to the current player.
- board[row][col] = player.
- Check every cell of the row, then of the column.
- If row == col, check the main diagonal; if row + col == n - 1, check the anti-diagonal.
- Return player if any checked line is full of their marks, else 0.
class TicTacToe {
private final int n;
private final int[][] board;
public TicTacToe(int n) {
this.n = n;
this.board = new int[n][n];
}
public int move(int row, int col, int player) {
board[row][col] = player;
boolean rowWin = true, colWin = true, diagWin = row == col, antiWin = row + col == n - 1;
for (int i = 0; i < n; i++) {
if (board[row][i] != player) rowWin = false;
if (board[i][col] != player) colWin = false;
if (board[i][i] != player) diagWin = false;
if (board[i][n - 1 - i] != player) antiWin = false;
}
return (rowWin || colWin || diagWin || antiWin) ? player : 0;
}
}class TicTacToe:
def __init__(self, n: int):
self.n = n
self.board = [[0] * n for _ in range(n)]
def move(self, row: int, col: int, player: int) -> int:
n, b = self.n, self.board
b[row][col] = player
row_win = col_win = True
diag_win = row == col
anti_win = row + col == n - 1
for i in range(n):
if b[row][i] != player:
row_win = False
if b[i][col] != player:
col_win = False
if b[i][i] != player:
diag_win = False
if b[i][n - 1 - i] != player:
anti_win = False
return player if (row_win or col_win or diag_win or anti_win) else 0class TicTacToe {
int n;
vector<vector<int>> board;
public:
TicTacToe(int n) : n(n), board(n, vector<int>(n, 0)) {}
int move(int row, int col, int player) {
board[row][col] = player;
bool rowWin = true, colWin = true, diagWin = row == col, antiWin = row + col == n - 1;
for (int i = 0; i < n; i++) {
if (board[row][i] != player) rowWin = false;
if (board[i][col] != player) colWin = false;
if (board[i][i] != player) diagWin = false;
if (board[i][n - 1 - i] != player) antiWin = false;
}
return (rowWin || colWin || diagWin || antiWin) ? player : 0;
}
};class TicTacToe {
constructor(n) {
this.n = n;
this.board = Array.from({ length: n }, () => new Array(n).fill(0));
}
move(row, col, player) {
const n = this.n, b = this.board;
b[row][col] = player;
let rowWin = true, colWin = true, diagWin = row === col, antiWin = row + col === n - 1;
for (let i = 0; i < n; i++) {
if (b[row][i] !== player) rowWin = false;
if (b[i][col] !== player) colWin = false;
if (b[i][i] !== player) diagWin = false;
if (b[i][n - 1 - i] !== player) antiWin = false;
}
return (rowWin || colWin || diagWin || antiWin) ? player : 0;
}
}2Optimal (signed line counters)
O(1) per moveEach move updates and checks at most four counters.O(n)Two arrays of n counters plus two diagonal counters.Drop the board. Keep one counter per row, one per column and one for each diagonal. Player 1 adds +1 and player 2 adds -1 to every line the move touches. Since cells are never reused, a line whose counter reaches n in absolute value is filled entirely by one player.
- rows[n], cols[n], diag, anti all start at 0.
- d = player == 1 ? 1 : -1.
- rows[row] += d; cols[col] += d; if row == col, diag += d; if row + col == n - 1, anti += d.
- If any of those four values has absolute value n, return player; else return 0.
class TicTacToe {
private final int n;
private final int[] rows, cols;
private int diag, anti;
public TicTacToe(int n) {
this.n = n;
this.rows = new int[n];
this.cols = new int[n];
}
public int move(int row, int col, int player) {
int d = player == 1 ? 1 : -1;
rows[row] += d;
cols[col] += d;
if (row == col) diag += d;
if (row + col == n - 1) anti += d;
if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n
|| Math.abs(diag) == n || Math.abs(anti) == n) {
return player;
}
return 0;
}
}class TicTacToe:
def __init__(self, n: int):
self.n = n
self.rows = [0] * n
self.cols = [0] * n
self.diag = 0
self.anti = 0
def move(self, row: int, col: int, player: int) -> int:
n = self.n
d = 1 if player == 1 else -1
self.rows[row] += d
self.cols[col] += d
if row == col:
self.diag += d
if row + col == n - 1:
self.anti += d
if (abs(self.rows[row]) == n or abs(self.cols[col]) == n
or abs(self.diag) == n or abs(self.anti) == n):
return player
return 0class TicTacToe {
int n;
vector<int> rows, cols;
int diag = 0, anti = 0;
public:
TicTacToe(int n) : n(n), rows(n, 0), cols(n, 0) {}
int move(int row, int col, int player) {
int d = player == 1 ? 1 : -1;
rows[row] += d;
cols[col] += d;
if (row == col) diag += d;
if (row + col == n - 1) anti += d;
if (abs(rows[row]) == n || abs(cols[col]) == n || abs(diag) == n || abs(anti) == n) {
return player;
}
return 0;
}
};class TicTacToe {
constructor(n) {
this.n = n;
this.rows = new Array(n).fill(0);
this.cols = new Array(n).fill(0);
this.diag = 0;
this.anti = 0;
}
move(row, col, player) {
const n = this.n;
const d = player === 1 ? 1 : -1;
this.rows[row] += d;
this.cols[col] += d;
if (row === col) this.diag += d;
if (row + col === n - 1) this.anti += d;
if (Math.abs(this.rows[row]) === n || Math.abs(this.cols[col]) === n
|| Math.abs(this.diag) === n || Math.abs(this.anti) === n) {
return player;
}
return 0;
}
}Edge cases to test
- A win on the anti-diagonal (row + col == n - 1)
- The center cell of an odd board lies on both diagonals
- n = 2, where two marks already complete a line
- A full board with no winner, so every move returns 0
Hints
Hint 1
After a move, only the row, the column and (maybe) the two diagonals through that cell can have become complete.
Hint 2
You never need the board itself: count how many marks each player has in every row, column and diagonal.
Hint 3
Use +1 for player 1 and -1 for player 2 in a single counter per line; a line is won when its counter reaches +n or -n.
FAQ
What is the best time complexity for Design Tic-Tac-Toe?
Optimal (signed line counters) runs in O(1) per move time and O(n) extra space. Each move updates and checks at most four counters.
Which pattern does Design Tic-Tac-Toe use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Design Tic-Tac-Toe?
Yes. Brute force (store the board, check the lines through the move) takes O(n) per move time and O(n²) space. Keep the full n x n grid.
Which edge cases should I test for Design Tic-Tac-Toe?
A win on the anti-diagonal (row + col == n - 1); The center cell of an odd board lies on both diagonals; n = 2, where two marks already complete a line; A full board with no winner, so every move returns 0.