Leetcode 348. Design Tic-Tac-Toe
Problem Explanation
The problem is to design a game of tic-tac-toe that can be played by two players on a grid of size n x n. In this game, two players take turns to play. Each player has their own symbol ('X' for player 1 and 'O' for player 2). Players take turns placing their symbol on the grid. The first player who manages to place their symbols in a complete vertical, horizontal, or diagonal line wins the game.
The input to the method 'move' will consist a row number, a column number and a player number in order. For each move, if no player has won the game, it returns 0. If player 1 wins it returns 1 and if player 2 wins it returns 2.
The task is to implement this game and method move
such that it determines the winner efficiently. An inefficient solution is to check the entire board after each move, which would be an O(n^2)
operation. The problem requires to come up with a better solution with time complexity lower than O(n^2)
.
Explanation of the Solution
We note that for each new move, only the row, column and the diagonals (if any) passing through the current cell get updated and therefore, affect the outcome of the game based on current move. To keep track of these, we maintain counts of 'X's and 'O's for each row, column and diagonals in the game.
Specifically, for each new move in row i
and column j
by player p
, we increment counters for row i
, column j
and the diagonals if i==j
or i+j==n-1
, where n
is the size of the board. For player 1, we increment the counters, and for player 2, we decrement them. If after the move, any of the counters becomes n
or -n
, player 1 or player 2 wins, respectively.
In the following, we present solutions based on this approach for different programming languages:
Python Solution
1 2python 3class TicTacToe: 4 5 def __init__(self, n: int): 6 self.n = n 7 self.rows = [0] * n 8 self.cols = [0] * n 9 self.diag = 0 10 self.anti_diag = 0 11 12 def move(self, row: int, col: int, player: int) -> int: 13 add = 1 if player == 1 else -1 14 15 self.rows[row] += add 16 self.cols[col] += add 17 if row == col: 18 self.diag += add 19 if row + col == self.n - 1: 20 self.anti_diag += add 21 22 if (abs(self.rows[row]) == self.n or 23 abs(self.cols[col]) == self.n or 24 abs(self.diag) == self.n or 25 abs(self.anti_diag) == self.n): 26 return player 27 return 0
Java Solution
1 2java 3public class TicTacToe { 4 private int[][] board; 5 private int[] rows; 6 private int[] cols; 7 private int n, diag, antiDiag; 8 9 public TicTacToe(int n) { 10 board = new int[n][n]; 11 rows = new int[n]; 12 cols = new int[n]; 13 this.n = n; 14 } 15 16 public int move(int row, int col, int player) { 17 int value = player == 1 ? 1 : -1; 18 19 rows[row] += value; 20 cols[col] += value; 21 if (row == col) { 22 diag += value; 23 } 24 if (row + col == n-1) { 25 antiDiag += value; 26 } 27 28 if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || 29 Math.abs(diag) == n || Math.abs(antiDiag) == n) { 30 return player; 31 } 32 33 return 0; 34 } 35}
JavaScript Solution
1
2javascript
3class TicTacToe {
4 constructor(n) {
5 this.rows = new Array(n).fill(0);
6 this.cols = new Array(n).fill(0);
7 this.diag = 0;
8 this.antiDiag = 0;
9 this.n = n;
10 }
11
12 move(row, col, player) {
13 let add = player === 1 ? 1 : -1;
14
15 this.rows[row] += add;
16 this.cols[col] += add;
17 if (row === col) {
18 this.diag += add;
19 }
20 if (row + col === this.n - 1) {
21 this.antiDiag += add;
22 }
23
24 if (Math.abs(this.rows[row]) === this.n ||
25 Math.abs(this.cols[col]) === this.n ||
26 Math.abs(this.diag) === this.n ||
27 Math.abs(this.antiDiag) === this.n) {
28 return player;
29 }
30
31 return 0;
32 }
33}
C++ Solution
1
2cpp
3class TicTacToe {
4public:
5 TicTacToe(int n) {
6 rows = vector<int>(n, 0);
7 cols = vector<int>(n, 0);
8 diag = 0;
9 antiDiag = 0;
10 this->n = n;
11 }
12
13 int move(int row, int col, int player) {
14 int add = player == 1 ? 1 : -1;
15
16 rows[row] += add;
17 cols[col] += add;
18 if (row == col) {
19 diag += add;
20 }
21 if (row + col == n - 1) {
22 antiDiag += add;
23 }
24
25 if (abs(rows[row]) == n || abs(cols[col]) == n || abs(diag) == n || abs(antiDiag) == n) {
26 return player;
27 }
28
29 return 0;
30 }
31
32private:
33 vector<int> rows;
34 vector<int> cols;
35 int diag, antiDiag, n;
36};
C# Solution
1
2csharp
3public class TicTacToe {
4
5 private int[] rows;
6 private int[] cols;
7 private int diag;
8 private int antiDiag;
9 private int n;
10
11 public TicTacToe(int n) {
12 this.rows = new int[n];
13 this.cols = new int[n];
14 this.n = n;
15 }
16
17 public int Move(int row, int col, int player) {
18 int add = player == 1 ? 1 : -1;
19
20 rows[row] += add;
21 cols[col] += add;
22 if (row == col) {
23 diag += add;
24 }
25 if (row + col == n - 1) {
26 antiDiag += add;
27 }
28
29 if (Math.Abs(rows[row]) == n || Math.Abs(cols[col]) == n ||
30 Math.Abs(diag) == n || Math.Abs(antiDiag) == n) {
31 return player;
32 }
33
34 return 0;
35 }
36}
As you can see, the implementation in every language follows the same logic as explained above.# Key Takeaways
What makes this solution efficient is that it checks only the relevant parts of the board after each move instead of checking the entire board. It maintains counters for each row, column, and diagonals, and increment the counters whenever a move is made. It avoids unnecessary repetition and reduces the time complexity significantly.
The solution adopts a "count as you go" approach, keeping track of the game's progression, which is much more time and space efficient than checking the entire grid repeatedly. This is an example of how we can use simple tools, such as arrays, to track certain criteria in the problem, drastically reducing time complexity.
This problem teaches the following concepts:
- How to maintain and update information dynamically to avoid repeated computations.
- How adding counters can significantly bring down time complexity.
- The importance of identifying and optimizing the parts of a problem that need to be checked repeatedly.
The suggested solutions, although presented for a game of tic-tac-toe, can also be useful in other similar problems where we have to keep track of the changes happening in real time. This method of computation can be expanded to accommodate larger grids, other games or more complex settings.
While these implementations take into account valid moves only, they can be expanded to include checks for invalid moves as well. Always remember, a key part to solving large programming problems is breaking them down into smaller parts and tackling those. In this case, breaking the grid down and monitoring them individually proved to be the effective solution.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.