Design Tic-Tac-Toe

Medium

Asked by:

+5

More companies

487 views

Topics:

Arrays

Assume n is the size of the game board. The Tic-Tac-Toe board is size n x n.

A move is guaranteed to be valid and is placed on an empty block.

A player who achieves n same marks (row, column, diagonal, or anti-diagonal) wins the game.

Implement the TicTacToe class:

TicTacToe(int n) Initializes the object with the size of the board n.
int move(int row, int col, int player) Indicates that player player moves at cell (row, col) on the board. The function returns:

0 if no one wins.
1 if player 1 wins.
2 if player 2 wins.

Example 1:

Input
["TicTacToe", "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]]
Output
[null, 0, 0, 0, 0, 0, 2]

Explanation
TicTacToe ticTacToe = new TicTacToe(3);
// Assume that player 1 is "X" and player 2 is "O"
Board after move("X", 0, 0) =
|	X	|	 	|	 	|
|	 	|	 	|	 	|
|	 	|	 	|	 	|
move("X", 0, 0); // return 0 (no one wins)
Board after move("O", 0, 2) =
|	X	|	 	|	O	|
|	 	|	 	|	 	|
|	 	|	 	|	 	|
move("O", 0, 2); // return 0 (no one wins)
Board after move("X", 2, 2) =
|	X	|	 	|	O	|
|	 	|	 	|	 	|
|	 	|	 	|	X	|
move("X", 2, 2); // return 0 (no one wins)
Board after move("O", 1, 1) =
|	X	|	 	|	O	|
|	 	|	O	|	 	|
|	 	|	 	|	X	|
move("O", 1, 1); // return 0 (no one wins)
Board after move("X", 2, 0) =
|	X	|	 	|	O	|
|	 	|	O	|	 	|
|	X	|	 	|	X	|
move("X", 2, 0); // return 0 (no one wins)
Board after move("O", 1, 0) =
|	X	|	 	|	O	|
|	O	|	O	|	 	|
|	X	|	 	|	X	|
move("O", 1, 0); // return 2 (player 2 wins, because there is a row with three 'O's).

Constraints:

2 <= n <= 100
player is 1 or 2.
0 <= row, col < n
(row, col) are valid and empty.
At most n² calls will be made to move.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the Tic-Tac-Toe board? Is it always a 3x3 grid, or could it be of variable size?
What is the expected format of the input sequence of moves? For example, will it be a list of tuples `(row, col, player)`, or a string representation?
How should the system handle invalid moves, such as moves outside the board boundaries, attempts to overwrite an existing move, or a player trying to move twice in a row?
What should be returned if the game ends in a draw? Is there a specific indicator, or a specific return value?
Can the input sequence of moves be empty? If so, what should be the output in that scenario?

Brute Force Solution

Approach

The brute force approach to designing Tic-Tac-Toe is like imagining every single possible game that could ever be played. We explore every move a player could make at each step of the game until the game ends.

Here's how the algorithm would work step-by-step:

Start at the beginning of an empty Tic-Tac-Toe board.
For the current player, consider every empty spot where they could place their mark.
For each possible move, imagine placing the mark and then consider what the other player could do next.
Continue this process, thinking through all the choices each player has at every turn.
Keep exploring all these branches of the game until someone wins or the board is full.
After exploring a complete game, rewind and try a different choice at an earlier step.
Do this for every single possible game from start to finish to see all outcomes.

Code Implementation

Big(O) Analysis

Time Complexity

O(9! * 9) – The brute force approach explores every possible game state. A Tic-Tac-Toe board has 9 cells. In the worst case, we explore all permutations of placing marks on these cells, which is 9 factorial (9!). At each step of exploring a game, we might check up to 9 cells to find an empty spot and potentially check for a win condition (which takes constant time relative to the total game states explored). Therefore, the total operations are proportional to 9! * 9, which simplifies to O(9!). Since 9! is a constant, the time complexity is effectively O(1) for a fixed-size board.

Space Complexity

O(1) – The brute force approach, as described, explores every possible game path. While this involves a significant number of recursive calls, each call only stores a few local variables and a single board state. Since the Tic-Tac-Toe board is fixed at 3x3 (a constant size, N=9), the depth of the recursion and the memory used per call remain constant regardless of the number of moves made. Therefore, the auxiliary space complexity is constant, O(1).

Optimal Solution

Approach

The optimal strategy for Tic-Tac-Toe involves representing the game board efficiently and then quickly checking for winning conditions after each move. We can avoid complex checks by focusing on what actually matters: a complete line of three for either player.

Here's how the algorithm would work step-by-step:

Imagine the game board as a simple grid where we can easily keep track of where each player has placed their marks.
When a player makes a move, we only need to check the specific row, column, and diagonal that their mark landed in to see if they've won.
Instead of checking all possible winning combinations every single time, we just focus on the immediate vicinity of the new mark.
We can maintain simple counts for each row, column, and diagonal, indicating how many marks of each player are present.
When a mark is placed, we update the corresponding counts. If a count reaches three for a player, they have won.
This way, we avoid repeatedly scanning the entire board and instead perform a very targeted and quick check after every move.

Code Implementation

class TicTacToe:

    def __init__(self, board_size):
        self.board_size = board_size
        self.rows_player1 = [0] * board_size
        self.rows_player2 = [0] * board_size
        self.columns_player1 = [0] * board_size
        self.columns_player2 = [0] * board_size
        self.diagonal_main_player1 = 0
        self.diagonal_main_player2 = 0
        self.diagonal_anti_player1 = 0
        self.diagonal_anti_player2 = 0
        self.moves_made = 0

    def move(self, player_identifier, row_index, column_index):
        # Player 1 is represented by 1, Player 2 by 2.
        if player_identifier == 1:
            self.rows_player1[row_index] += 1
            self.columns_player1[column_index] += 1
            # Check if the move is on the main diagonal.
            if row_index == column_index:
                self.diagonal_main_player1 += 1
            # Check if the move is on the anti-diagonal.
            if row_index + column_index == self.board_size - 1:
                self.diagonal_anti_player1 += 1

            # Winning condition must be checked after each player's move.
            if self.rows_player1[row_index] == self.board_size or \
               self.columns_player1[column_index] == self.board_size or \
               self.diagonal_main_player1 == self.board_size or \
               self.diagonal_anti_player1 == self.board_size:
                return 1
        else:
            self.rows_player2[row_index] += 1
            self.columns_player2[column_index] += 1
            # Check if the move is on the main diagonal.
            if row_index == column_index:
                self.diagonal_main_player2 += 1
            # Check if the move is on the anti-diagonal.
            if row_index + column_index == self.board_size - 1:
                self.diagonal_anti_player2 += 1

            # Winning condition must be checked after each player's move.
            if self.rows_player2[row_index] == self.board_size or \
               self.columns_player2[column_index] == self.board_size or \
               self.diagonal_main_player2 == self.board_size or \
               self.diagonal_anti_player2 == self.board_size:
                return 2

        self.moves_made += 1
        # Return 0 if no winner and game is not a draw.
        if self.moves_made == self.board_size * self.board_size:
            return 0
        else:
            return -1

Big(O) Analysis

Time Complexity

O(1) – The strategy focuses on updating and checking counts for rows, columns, and diagonals. Since the board size is fixed (3x3), the number of rows (3), columns (3), and diagonals (2) is constant. Updating and checking these counts after each move takes a fixed number of operations, irrespective of the total number of moves made. Therefore, the time complexity for checking a win condition is constant.

Space Complexity

O(1) – The provided solution uses a fixed number of variables to store counts for rows, columns, and diagonals, irrespective of the game board size. No dynamic data structures whose size depends on the input size are created. Therefore, the auxiliary space complexity remains constant, denoted as O(1).

Edge Cases

Case	How to Handle
Null or empty list of moves	An empty or null input should result in the game state being 'ongoing' with no winner or draw.
Moves exceeding the 3x3 board dimensions	Moves with row or column indices outside the 0-2 range should be considered invalid and potentially ignored or raise an error.
Duplicate moves at the same row and column	The system should handle subsequent moves to an already occupied cell by either ignoring them or flagging an error, depending on strictness.
Moves made after a player has already won	The system should recognize a win state and ideally stop processing further moves, or at least not alter the game state once a winner is declared.
A full board with no winner (draw condition)	The system must correctly identify a draw when all 9 cells are filled and no player has met the winning criteria.
A sequence of moves that could lead to simultaneous wins if not checked sequentially	The game state should be checked after each individual move to declare the winner as soon as the winning condition is met.
A player making moves of the wrong type (not 'X' or 'O')	Invalid player characters should be rejected or flagged as errors to maintain game integrity.
The total number of moves being less than 5 (minimum for a potential win)	The system should correctly report the game as 'ongoing' if insufficient moves have been made to possibly achieve a win.

Null or empty list of moves

How to Handle:

An empty or null input should result in the game state being 'ongoing' with no winner or draw.

Moves exceeding the 3x3 board dimensions

How to Handle:

Moves with row or column indices outside the 0-2 range should be considered invalid and potentially ignored or raise an error.

Duplicate moves at the same row and column

How to Handle:

The system should handle subsequent moves to an already occupied cell by either ignoring them or flagging an error, depending on strictness.

Moves made after a player has already won

How to Handle:

The system should recognize a win state and ideally stop processing further moves, or at least not alter the game state once a winner is declared.

A full board with no winner (draw condition)

How to Handle:

The system must correctly identify a draw when all 9 cells are filled and no player has met the winning criteria.

A sequence of moves that could lead to simultaneous wins if not checked sequentially

How to Handle:

The game state should be checked after each individual move to declare the winner as soon as the winning condition is met.

A player making moves of the wrong type (not 'X' or 'O')

How to Handle:

Invalid player characters should be rejected or flagged as errors to maintain game integrity.

The total number of moves being less than 5 (minimum for a potential win)

How to Handle:

The system should correctly report the game as 'ongoing' if insufficient moves have been made to possibly achieve a win.