348. Design Tic-Tac-Toe
Problem Description
The given problem describes a tic-tac-toe game which is generalized for an n x n
board, as opposed to the traditional 3 x 3
board. Two players take turns to place their mark on the board. The goal for each player is to get n
of their own marks in a row, either horizontally, vertically, or diagonally. The challenge is to implement a class TicTacToe
that can process each move made by the players and determine the status of the game after each move, specifically:
- If the game continues with no winner.
- If player 1 has won.
- If player 2 has won.
Intuition
The main concept behind the solution is keeping track of the number of marks each player has in each row, column, and diagonal. We can achieve this by using an array or a list where each index represents the count of marks for a particular row, column, or diagonal. Each player has their own separate array of counts.
When a player makes a move, we increment the counts at the relevant indices, which correspond to the row and column of the move, and the two diagonals if applicable (when the move is on either of the diagonals). After updating the counts, we only need to check the counts of the current move's row, column, and possibly the diagonals. If any of these counts reach n
, it signifies that n
marks of the same player are aligned, and that player wins.
Specifically for diagonals, we can observe two properties:
- The indices for the primary diagonal (
row == col
) are the same, so we can use a single counter for the entire diagonal. - The indices for the secondary diagonal (
row + col == n - 1
) also form a unique pattern, allowing us to use another single counter.
Let's create a two-dimensional list (or array) called counter
, with two rows (one for each player) and 2n + 2
columns to cover all rows, all columns, and the two diagonals. We use player - 1
as the index to access the correct row in counter
for the current player (since player ID is either 1 or 2, while list indexing starts from 0).
Every call to the move
method updates these counts and checks for a win condition, returning 0 if there is no winner, 1 if player 1 wins, or 2 if player 2 wins. By only checking the counts related to the last move, we efficiently determine the outcome without re-scanning the entire board after every move.
Solution Approach
The implementation of the TicTacToe
class uses a methodical approach influenced by the need for efficiency in processing moves on an n x n
tic-tac-toe board. The code consists of two primary components: the constructor __init__
and the method move
.
In the __init__
method, we initialize two core elements:
self.n
: Store the size of the board, which is used across the class to check for win conditions.self.counter
: A two-dimensional list (with dimensions 2x(2n + 2)) that holds the count of marks for both players across all rows, columns, and both diagonals. The rows represent each player (player 1 and player 2), while the columns represent the actual counts for each row, each column, and the two diagonals of the board. Note that we use a bit shift (n << 1
) which is essentially doublingn
, to determine the positions in thecounter
array where we track the diagonals.
The move
method is the crux of the solution and is designed to handle a player's turn:
-
It increments the counts in
self.counter
for the current player by updating:- The entry corresponding to the current
row
. - The entry corresponding to the current
col
, offset byn
to position it in the column-tracking part of thecounter
. - If the move is on the primary diagonal (where
row == col
), we increment the entry at positionn << 1
. - If the move is on the secondary diagonal (where
row + col == n - 1
), we increment the entry at position(n << 1) + 1
.
- The entry corresponding to the current
-
After the move, the method checks if any of the counts (current row, column, or diagonals) have reached
n
. If so, we have a winner (the currentplayer
), and we return theplayer
's number (1 or 2). If no winning condition is met, we return 0 to indicate that the game continues with no winner yet.
This solution uses the properties of a tic-tac-toe game board and simple arithmetic to keep track of potential winning conditions, which allows for constant time (O(1)) processing of each move regardless of the board size, making it highly efficient even as n
increases.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example. Consider a 3x3
tic-tac-toe board, where n = 3
. We want to simulate a few moves using the TicTacToe
class to see how it tracks the game's status.
Initial Setup
We begin by initializing the game with n = 3
, which will internally create a counter
list with dimensions 2x(2*3 + 2) = 2x8
. This counter will hold the count of marks for both players across all rows, columns, and both diagonals.
Process Moves
Suppose the following series of moves:
- Player 1 places a mark at position (0, 0).
- Player 2 places a mark at position (1, 1).
- Player 1 places a mark at position (1, 0).
- Player 2 places a mark at position (2, 2).
- Player 1 places a mark at position (2, 0).
Turn-by-Turn Walkthrough
Now, let's walk through the moves one by one and see how the move
method updates the counter
and checks for a winner.
-
Turn 1: Player 1
(0, 0)
- Counter before move =
[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
- Move updates row 0 and column 0, and primary diagonal because it's the 0th position (
row == col
). - Counter after move =
[[1, 0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
- No winner yet, so it returns
0
.
- Counter before move =
-
Turn 2: Player 2
(1, 1)
- Counter before move =
[[1, 0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
- Move updates row 1 and column 1, and both diagonals because it's center of the board (
row == col
androw + col == n - 1
). - Counter after move =
[[1, 0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- No winner yet, so it returns
0
.
- Counter before move =
-
Turn 3: Player 1
(1, 0)
- Counter before move =
[[1, 0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- Move updates row 1 and column 0 only.
- Counter after move =
[[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- No winner yet, so it returns
0
.
- Counter before move =
-
Turn 4: Player 2
(2, 2)
- Counter before move =
[[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1, 1]]
- Move updates row 2, column 2, and both diagonals since
row + col == n - 1
. - Counter after move =
[[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 2, 2]]
- No winner yet, so it returns
0
.
- Counter before move =
-
Turn 5: Player 1
(2, 0)
- Counter before move =
[[1, 1, 0, 2, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 2, 2]]
- Move updates row 2, column 0, no diagonals aligned.
- Counter after move =
[[1, 2, 0, 3, 0, 0, 1, 0], [0, 1, 1, 0, 1, 1, 2, 2]]
- The counter for row 2 (third row of the board) has reached
3
, which means Player 1 hasn
marks in a row and wins. - It returns
1
, indicating Player 1 wins.
- Counter before move =
After each move, only the scores in the counter that have been updated need to be checked. The returning value after the last move indicates if there is a winner or if the game continues.
Solution Implementation
1class TicTacToe:
2 def __init__(self, n: int):
3 """
4 Initialize the TicTacToe game board with a given size.
5 """
6 self.board_size = n
7 # self.counters store the counts for (rows, columns, diagonal, anti-diagonal)
8 # self.counters[player][i]:
9 # i from 0 to n-1 (row counts), i from n to 2*n-1 (column counts),
10 # i equals 2*n (main diagonal count), i equals 2*n + 1 (anti-diagonal count)
11 # Index 0: player 1, Index 1: player 2
12 self.counters = [[0] * (2 * n + 2) for _ in range(2)]
13
14 def move(self, row: int, col: int, player: int) -> int:
15 """
16 Player makes a move at a specified row and column.
17 :param row: The row index of the board, 0-indexed.
18 :param col: The column index of the board, 0-indexed.
19 :param player: The identifier of the player (either 1 or 2).
20 :return: The current winning condition, can be either:
21 0: No one wins.
22 1: Player 1 wins.
23 2: Player 2 wins.
24 """
25 player_index = player - 1 # Convert to 0-indexing for players 1 and 2
26 diagonal_index = 2 * self.board_size
27 anti_diagonal_index = 2 * self.board_size + 1
28
29 # Update the row, column, and possibly the diagonal counts for the move
30 self.counters[player_index][row] += 1 # Row count
31 self.counters[player_index][col + self.board_size] += 1 # Column count
32 if row == col:
33 self.counters[player_index][diagonal_index] += 1 # Diagonal count
34 if row + col == self.board_size - 1:
35 self.counters[player_index][anti_diagonal_index] += 1 # Anti-diagonal count
36
37 # Check if any count has reached the board size, which means a win.
38 if (
39 self.counters[player_index][row] == self.board_size
40 or self.counters[player_index][col + self.board_size] == self.board_size
41 or self.counters[player_index][diagonal_index] == self.board_size
42 or self.counters[player_index][anti_diagonal_index] == self.board_size
43 ):
44 return player # The current player wins
45
46 # If no win, return 0 indicating no winner yet
47 return 0
48
49
50# Example of how the TicTacToe class is used:
51# game = TicTacToe(n)
52# result = game.move(row, col, player)
53
1public class TicTacToe {
2
3 private int size; // Size of the board (n x n)
4 private int[][] moveCounters; // Array to keep track of the count of moves for both players
5
6 /**
7 * Constructor to initialize the board of given size.
8 *
9 * @param n Size of the TicTacToe board.
10 */
11 public TicTacToe(int n) {
12 // Initialize counter for rows, columns, the main diagonal, and the anti-diagonal.
13 // For each player, we need n counters for rows, n for columns, one for the main diagonal,
14 // and one for the anti-diagonal.
15 moveCounters = new int[2][n * 2 + 2]; // 0 index for player 1 and 1 index for player 2
16 this.size = n;
17 }
18
19 /**
20 * Records a move by the player, checks the winning condition, and returns the game state.
21 *
22 * @param row The row where the move is made.
23 * @param col The column where the move is made.
24 * @param player The id of the player making the move, can be either 1 or 2.
25 * @return The game state after the move: 0 means no one wins, 1 means player 1 wins, 2 means player 2 wins.
26 */
27 public int move(int row, int col, int player) {
28 // Increment the corresponding row and column counters for the player.
29 moveCounters[player - 1][row]++; // Increment row counter for the player
30 moveCounters[player - 1][col + size]++; // Increment column counter for the player
31
32 // If the move is on the main diagonal, increment the main diagonal counter.
33 if (row == col) {
34 moveCounters[player - 1][size * 2]++;
35 }
36
37 // If the move is on the anti-diagonal, increment the anti-diagonal counter.
38 if (row + col == size - 1) {
39 moveCounters[player - 1][size * 2 + 1]++;
40 }
41
42 // Check each counter for the player to see if they've reached 'size';
43 // meaning they've filled a row, column, or diagonal.
44 if (moveCounters[player - 1][row] == size
45 || moveCounters[player - 1][col + size] == size
46 || moveCounters[player - 1][size * 2] == size
47 || moveCounters[player - 1][size * 2 + 1] == size) {
48 return player; // The player has won the game.
49 }
50
51 return 0; // No one has won the game yet.
52 }
53}
54
55/**
56 * Usage example:
57 * TicTacToe ticTacToe = new TicTacToe(3);
58 * int gameResult = ticTacToe.move(0, 0, 1); // Move by player 1
59 * gameResult = ticTacToe.move(1, 1, 2); // Move by player 2
60 * ... // Continues game play
61 */
62
1#include <vector>
2
3class TicTacToe {
4private:
5 int size; // Size of the board (n x n)
6 std::vector<std::vector<int>> moveCounters; // 2D vector to keep track of the count of moves for both players
7
8public:
9 /**
10 * Constructor to initialize the board of given size.
11 *
12 * @param n Size of the TicTacToe board.
13 */
14 TicTacToe(int n) : size(n), moveCounters(2, std::vector<int>(2 * n + 2, 0)) {
15 // The moveCounters vector keeps track of each player's move counts on rows, columns,
16 // main diagonal, and anti-diagonal.
17 // Index 0 for player 1 and 1 for player 2.
18 // The counts for rows are stored in [i][0 to n-1], for columns in [i][n to 2*n-1],
19 // main diagonal in [i][2*n], and anti-diagonal in [i][2*n + 1].
20 }
21
22 /**
23 * Records a move by the player, checks the winning condition and returns the game state.
24 *
25 * @param row The row where the move is made.
26 * @param col The column where the move is made.
27 * @param player The id of the player making the move, can be either 1 or 2.
28 * @return The game state after the move: 0 means no one wins, 1 means player 1 wins, 2 means player 2 wins.
29 */
30 int move(int row, int col, int player) {
31 int playerIndex = player - 1; // Adjust player id to index (0 or 1 for player 1 or 2 respectively)
32
33 // Increment the corresponding row and column counters for the player.
34 moveCounters[playerIndex][row]++; // Increment row counter for the player
35 moveCounters[playerIndex][col + size]++; // Increment column counter for the player
36
37 // If the move is on the main diagonal, increment the main diagonal counter.
38 if (row == col) {
39 moveCounters[playerIndex][size * 2]++;
40 }
41
42 // If the move is on the anti-diagonal, increment the anti-diagonal counter.
43 if (row + col == size - 1) {
44 moveCounters[playerIndex][size * 2 + 1]++;
45 }
46
47 // Check the counters for the player to see if they've reached 'size',
48 // which would mean they've filled a row, column, or diagonal.
49 if (moveCounters[playerIndex][row] == size
50 || moveCounters[playerIndex][col + size] == size
51 || moveCounters[playerIndex][size * 2] == size
52 || moveCounters[playerIndex][size * 2 + 1] == size) {
53 return player; // The player has won the game.
54 }
55
56 return 0; // No one has won the game yet.
57 }
58};
59
60/**
61 * Usage example:
62 *
63 * TicTacToe ticTacToe(3);
64 * int gameResult = ticTacToe.move(0, 0, 1); // Move by player 1
65 * gameResult = ticTacToe.move(1, 1, 2); // Move by player 2
66 * ... // Continues game play
67 */
68
1// Size of the TicTacToe board (n x n).
2let size: number;
3
4// Array to keep track of the count of moves for both players.
5let moveCounters: number[][];
6
7// Initialize the board of given size.
8// n: Size of the TicTacToe board.
9function initializeGame(n: number): void {
10 // Initialize counter for rows, columns, the main diagonal, and the anti-diagonal.
11 // For each player, we need n counters for rows, n for columns, one for the main diagonal,
12 // and one for the anti-diagonal.
13 moveCounters = [[],[]]; // Index 0 for player 1 and index 1 for player 2
14 for(let i = 0; i < 2; i++) { // Initialize all counters to zero.
15 for(let j = 0; j < n * 2 + 2; j++){
16 moveCounters[i][j] = 0;
17 }
18 }
19 size = n;
20}
21
22// Records a move by the player, checks the winning condition, and returns the game state.
23// row: The row where the move is made.
24// col: The column where the move is made.
25// player: The id of the player making the move, can be either 1 or 2.
26// Returns: The game state after the move: 0 means no one wins, 1 means player 1 wins, 2 means player 2 wins.
27function move(row: number, col: number, player: number): number {
28 // Increment the corresponding row and column counters for the player.
29 moveCounters[player - 1][row]++; // Increment row counter for the player
30 moveCounters[player - 1][col + size]++; // Increment column counter for the player
31
32 // If the move is on the main diagonal, increment the main diagonal counter.
33 if (row === col) {
34 moveCounters[player - 1][size * 2]++;
35 }
36
37 // If the move is on the anti-diagonal, increment the anti-diagonal counter.
38 if (row + col === size - 1) {
39 moveCounters[player - 1][size * 2 + 1]++;
40 }
41
42 // Check if any counter for the player has reached 'size' for a victory.
43 if (moveCounters[player - 1][row] === size ||
44 moveCounters[player - 1][col + size] === size ||
45 moveCounters[player - 1][size * 2] === size ||
46 moveCounters[player - 1][size * 2 + 1] === size) {
47 return player; // The player has won the game.
48 }
49
50 return 0; // No one has won the game yet.
51}
52
53// Usage example
54initializeGame(3);
55let gameResult = move(0, 0, 1); // Move by player 1
56gameResult = move(1, 1, 2); // Move by player 2
57// ... Continue game play
58
Time and Space Complexity
Time Complexity
The time complexity for the move
method in the TicTacToe class is O(1)
. This is because the method executes a constant number of operations for any given move, regardless of the size of the board.
In each call to move
, the method updates the corresponding counters for rows, columns, and diagonals based on the player's choice, which are direct accesses and increments in the self.counter
2D list. The checks for a win condition also involve constant-time comparisons since we are only checking if any row, column, or diagonal has reached the count n
.
Space Complexity
The space complexity for the TicTacToe class is O(n)
. This complexity comes from the need to store counts for each row, each column, and the two diagonals.
There are 2n
counters for rows and columns (since there are n
of each, and each player has their own counters), plus an additional 2 counters for the two diagonals (again separate for each player). Therefore, the counter array has a size of 2 * (n + n + 2)
which simplifies to 4n + 4
. The additional 4
is a constant that does not impact the space complexity in terms of O
notation, meaning the space usage is linear with respect to the size of the board.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!