Design Tic-Tac-Toe

Medium

Two Sigma

1 view

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.

Design Tic-Tac-Toe

Medium

Two Sigma

1 view

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.

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:

Will the game board always be a standard 3x3, or should the size be configurable for an NxN board?
What data type should represent the players (e.g., 'X' and 'O', or 1 and 2)?
Who makes the first move, or does my class need to determine this?
How should I handle invalid moves (e.g., placing a mark on an occupied cell)? Should I throw an exception, return an error code, or print an error message?
Beyond checking for a win, do I need to handle the case where the board is full (a draw/tie)? If so, what should my method return in this case?

Brute Force Solution

Approach

For Tic-Tac-Toe, a brute force approach means checking every possible move after each player's turn to see if anyone has won. We essentially simulate the game from the current state to all possible end states. We don't need to store past moves, we just need to check for a win after each one.

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

After each move by either player, examine the entire game board.
Check every row to see if all the positions in that row are filled with the same player's symbol (either all X's or all O's).
Check every column to see if all the positions in that column are filled with the same player's symbol.
Check both diagonals to see if all the positions in each diagonal are filled with the same player's symbol.
If any of these checks result in a row, column, or diagonal being filled with the same symbol, that player has won.
If no player has won, and all positions on the board are filled, then the game is a draw.
Repeat this process after every move until a player wins or the game ends in a draw.

Code Implementation

class TicTacToe:

    def __init__(self, board_size):
        self.board_size = board_size
        self.board = [['' for _ in range(board_size)] for _ in range(board_size)]
        self.current_player = 'X'

    def make_move(self, row, column):
        if self.board[row][column] == '':
            self.board[row][column] = self.current_player
            if self.check_win(self.current_player):
                return self.current_player
            elif self.check_draw():
                return 'Draw'
            else:
                self.current_player = 'O' if self.current_player == 'X' else 'X'
                return None
        else:
            return 'Invalid Move'

    def check_win(self, player):
        # Check rows and columns for a win
        for i in range(self.board_size):

            if all(self.board[i][j] == player for j in range(self.board_size)):
                return True
            if all(self.board[j][i] == player for j in range(self.board_size)):
                return True

        # Check diagonals for a win
        if all(self.board[i][i] == player for i in range(self.board_size)):
            return True
        if all(self.board[i][self.board_size - 1 - i] == player for i in range(self.board_size)):
            return True

        return False

    def check_draw(self):
        # Check if the board is full
        for row in self.board:
            if '' in row:
                return False
        return True

    def print_board(self):
        for row in self.board:
            print('| ' + ' | '.join(row) + ' |')

# Example Usage:
if __name__ == '__main__':
    game = TicTacToe(3)
    game.print_board()

    while True:
        row = int(input(f"Player {game.current_player}, enter row (0-{game.board_size-1}): "))
        column = int(input(f"Player {game.current_player}, enter column (0-{game.board_size-1}): "))

        result = game.make_move(row, column)
        game.print_board()

        if result == 'Invalid Move':
            print("Invalid move. Try again.")
        elif result:
            print(f"{result}!
")
            break

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The described brute force solution for Tic-Tac-Toe, after each move, examines the entire n x n game board to check for a win. It iterates through n rows, n columns, and two diagonals. Checking each row, column or diagonal takes O(n) time. Thus, after each move, the win condition check involves examining 2n rows+columns + 2 diagonals *O(n) check each which simplifies to O(n) in total after each move.

Space Complexity

O(1) – The described brute force approach for Tic-Tac-Toe primarily involves examining the game board directly after each move. It doesn't necessitate any extra data structures for storing intermediate results or past moves. The checks for rows, columns, and diagonals are performed in place, utilizing only a few variables to track the current position being checked. Consequently, the auxiliary space used remains constant, irrespective of the size (N) of the Tic-Tac-Toe board (N is implicitly the board size, which is fixed). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to simulate the game of Tic-Tac-Toe. The efficient strategy is to directly update the board's state and track winning conditions whenever a player makes a move.

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

Create a game board to represent the Tic-Tac-Toe grid.
When a player makes a move, update the corresponding position on the board with their symbol.
After each move, check if the current player has won by examining rows, columns, and diagonals.
If a player has won, declare the winner and end the game.
If no player has won after all positions are filled, declare a draw.
The clever thing is that we're checking for wins after *every* move, preventing wasted effort.

Code Implementation

class TicTacToe:
    def __init__(self, board_size):
        self.board_size = board_size
        self.game_board = [[' ' for _ in range(board_size)] for _ in range(board_size)]
        self.current_player = 'X'
    
    def move(self, row, column):
        if self.game_board[row][column] != ' ':
            return False
        
        self.game_board[row][column] = self.current_player
        
        if self.check_win(row, column):
            print(f'Player {self.current_player} wins!')
            return True
        
        if self.check_draw():
            print('Its a draw!')
            return True
        
        self.current_player = 'O' if self.current_player == 'X' else 'X'
        return True
    
    def check_win(self, row, column):
        # Check row
        if all(self.game_board[row][i] == self.current_player for i in range(self.board_size)):
            return True
        
        # Check column
        if all(self.game_board[i][column] == self.current_player for i in range(self.board_size)):
            return True
        
        # Check diagonal (top-left to bottom-right)
        if row == column and all(self.game_board[i][i] == self.current_player for i in range(self.board_size)):
            return True
        
        # Check diagonal (top-right to bottom-left)
        if row + column == self.board_size - 1 and all(self.game_board[i][self.board_size - 1 - i] == self.current_player for i in range(self.board_size)):
            return True
        
        return False
    
    def check_draw(self):
        # Check if the board is full
        if all(self.game_board[i][j] != ' ' for i in range(self.board_size) for j in range(self.board_size)):
            return True
        return False

    def print_board(self):
        for row in self.game_board:
            print('| ' + ' | '.join(row) + ' |')

# Example usage:
# game = TicTacToe(3)
# game.print_board()
# game.move(0, 0)
# game.print_board()

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(1) – The board size is fixed at 3x3. After each move, we check a constant number of rows, columns, and diagonals (specifically 3 rows, 3 columns, and 2 diagonals) to determine if a player has won. Since the number of checks is independent of any input size n and remains constant, the time complexity of checking for a win is O(1). Updating the board also takes O(1) time. Therefore, the overall time complexity for each move is O(1).

Space Complexity

O(1) – The algorithm utilizes a fixed-size game board (e.g., a 3x3 array for standard Tic-Tac-Toe). Regardless of the number of moves (which are bounded by the board size), the algorithm only needs to store the board's state, which has a constant size. Checking for wins involves examining rows, columns, and diagonals directly on the existing board, without allocating significant extra memory. Therefore, the auxiliary space used is constant, independent of any variable input size N, making the space complexity O(1).

Edge Cases

Case	How to Handle
Null or empty game board size	Throw IllegalArgumentException or return error code if size is null/zero/negative, as a valid board must have a positive dimension.
Invalid player value (not 1 or 2)	Throw IllegalArgumentException if the player value is not 1 or 2.
Row or column index out of bounds	Throw IndexOutOfBoundsException or return false if the move is out of bounds of the game board.
Cell already occupied	Return false if the specified cell already contains a move from another player.
Game already won	Return -1 if the game has already been won, indicating no further moves are possible.
Large board size (e.g., 1000x1000)	The solution should use O(1) space for tracking wins per row/col/diag, making it memory efficient.
Integer overflow when calculating win condition for large board sizes with many moves.	Using integer array to store moves per row/col/diag mitigates integer overflow risks because game ends before hitting max int.
Game ends in a draw (no winner and board is full)	The solution should return 0 if all cells are filled and there is no winner.