Find Winner on a Tic Tac Toe Game

#29 Most AskedEasy

Find Winner on a Tic Tac Toe Game #29 Most Asked

Easy

Tesla

7 views

Topics:

Arrays

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

Players take turns placing characters into empty squares ' '.
The first player A always places 'X' characters, while the second player B always places 'O' characters.
'X' and 'O' characters are always placed into empty squares, never on filled ones.
The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Given a 2D integer array moves where moves[i] = [row_i, col_i] indicates that the i^th move will be played on grid[row_i][col_i]. return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.

Constraints:

1 <= moves.length <= 9
moves[i].length == 2
0 <= row_i, col_i <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

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 possible values in the moves array, and what do they represent in terms of board coordinates?
Is the board size always 3x3, or can it be a different size (e.g., NxN)?
What should the function return if the game is still in progress (not won by either player and no more moves possible)?
Is the input `moves` guaranteed to be a valid sequence of moves, alternating between players and within the board boundaries?
If the game ends in a draw (all cells filled, and no winner), what should the function return?

Brute Force Solution

Approach

The brute force approach to finding the Tic Tac Toe winner involves checking every single possible way a player could win after each move is made. This means after each placement, we examine all rows, columns, and diagonals to see if they now contain three of the same mark.

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

After each player makes a move, examine the game board.
Check if any row now contains three of the same player's mark.
Check if any column now contains three of the same player's mark.
Check if either diagonal now contains three of the same player's mark.
If any of these conditions are true, that player is the winner.
If all the moves are finished and no player has won, then the game is a draw.
If none of the above conditions are true and moves remain, continue to the next move.

Code Implementation

def find_winner_tic_tac_toe(moves):
    board_size = 3
    board = [['' for _ in range(board_size)] for _ in range(board_size)]
    player_one = 'A'
    player_two = 'B'

    for move_index, move in enumerate(moves):
        row_coordinate, column_coordinate = move
        current_player = player_one if move_index % 2 == 0 else player_two
        board[row_coordinate][column_coordinate] = current_player

        # Check for a winner after each move
        if move_index >= 2:

            # Check rows for a win
            for row_index in range(board_size):
                if board[row_index][0] == board[row_index][1] == board[row_index][2] != '':
                    return board[row_index][0]

            # Check columns for a win
            for column_index in range(board_size):
                if board[0][column_index] == board[1][column_index] == board[2][column_index] != '':
                    return board[0][column_index]

            # Check diagonals for a win
            if board[0][0] == board[1][1] == board[2][2] != '':
                return board[0][0]
            if board[0][2] == board[1][1] == board[2][0] != '':
                return board[0][2]

    # Check if the game is a draw
    if len(moves) == board_size * board_size:
        return 'Draw'

    # If no winner and moves remain, the game is pending
    return 'Pending'

Big(O) Analysis

Time Complexity

O(1) – The input is an array of moves for a 3x3 Tic Tac Toe board. For each move, the algorithm checks all rows, columns, and diagonals to determine the winner. The size of the Tic Tac Toe board is fixed (3x3), meaning the number of checks performed after each move is constant and independent of the number of moves. Therefore, even though the moves array could have up to 9 elements, the operations within the function for checking winner are always bounded by constant checks for rows, columns, and diagonals, resulting in constant time complexity, O(1).

Space Complexity

O(1) – The provided solution involves examining the game board after each move to check rows, columns, and diagonals. This check is performed in-place, without using auxiliary data structures that scale with the number of moves or the size of the board. The space used is limited to a few variables for indexing and comparison during the win condition checks, which remains constant regardless of the number of moves (N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We don't need to check every possible winning line after each move. The best approach is to keep track of how close each player is to winning as the game goes on. This way, we only need to check for a winner once someone has a potential winning line completed.

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

Think of the Tic Tac Toe board as having rows, columns, and diagonals.
For each move made, mark that the player is one step closer to completing the row, column, and any diagonals the move is a part of.
After each move, check if the player who just moved has completed any row, column, or diagonal. If they have, that player is the winner.
If no one has won after all the moves are made, but every spot is filled, then the game is a draw.
If the game isn't over and there are still moves to be made, then no one has won yet and the game is still pending.

Code Implementation

def find_winner_on_tic_tac_toe_game(moves):
    board_size = 3
    row_counts_player_one = [0] * board_size
    column_counts_player_one = [0] * board_size
    diagonal_count_player_one = 0
    anti_diagonal_count_player_one = 0
    row_counts_player_two = [0] * board_size
    column_counts_player_two = [0] * board_size
    diagonal_count_player_two = 0
    anti_diagonal_count_player_two = 0

    for move_index, move in enumerate(moves):
        row, column = move
        player = (move_index % 2) + 1

        if player == 1:
            row_counts_player_one[row] += 1
            column_counts_player_one[column] += 1

            if row == column:
                diagonal_count_player_one += 1

            if row + column == board_size - 1:
                anti_diagonal_count_player_one += 1

            # Check win condition after each move
            if (row_counts_player_one[row] == board_size or\
                column_counts_player_one[column] == board_size or\
                diagonal_count_player_one == board_size or\
                anti_diagonal_count_player_one == board_size):

                return "A"
        else:
            row_counts_player_two[row] += 1
            column_counts_player_two[column] += 1

            if row == column:
                diagonal_count_player_two += 1

            if row + column == board_size - 1:
                anti_diagonal_count_player_two += 1

            # Check win condition after each move
            if (row_counts_player_two[row] == board_size or\
                column_counts_player_two[column] == board_size or\
                diagonal_count_player_two == board_size or\
                anti_diagonal_count_player_two == board_size):

                return "B"

    # If all moves are made and no winner, it's a draw.
    if len(moves) == board_size * board_size:
        return "Draw"

    # If moves remain and no winner, the game is pending.
    return "Pending"

Big(O) Analysis

Time Complexity

O(n) – The code iterates through the input moves array once, where n is the number of moves. For each move, we update counters for rows, columns, and diagonals, which takes constant time. After each move, we check if the current player has won, which also takes constant time. Therefore, the overall time complexity is directly proportional to the number of moves, resulting in O(n).

Space Complexity

O(1) – The provided plain English explanation indicates tracking how close each player is to winning by marking progress towards completing rows, columns, and diagonals. This could be achieved with a fixed number of counters or variables representing the state of each row, column, and diagonal for both players on a 3x3 board. Since the Tic Tac Toe board size is fixed (3x3), the number of rows, columns, and diagonals is also fixed, meaning the space needed for these counters remains constant, regardless of the input moves. Thus, the auxiliary space used is constant, independent of the number of moves made, leading to O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty moves array	Return 'Pending' immediately as the game hasn't started.
Invalid move coordinates (out of board bounds)	Throw an IllegalArgumentException or return an error string like 'Invalid Move' since the board is only 3x3.
A move is placed on an already occupied cell	Throw an IllegalArgumentException or return an error string, indicating invalid move as it violates the rules.
Moves do not alternate between players (e.g., player A moves twice in a row)	Maintain player turn information to ensure correct alternation and return an error if it's violated.
Game ends before all 9 moves are made with no winner	After all moves are processed and no winner is found, return 'Draw'.
Input contains only moves by player A or player B	The algorithm should check for alternating moves and return an error if moves are not alternating.
A player wins before all possible moves are made	The algorithm should detect the win and return 'A' or 'B' immediately.
The input contains negative values or non-integer values	The algorithm should validate the input and throw an exception, or return an appropriate error string to indicate invalid input.

Null or empty moves array

How to Handle:

Return 'Pending' immediately as the game hasn't started.

Invalid move coordinates (out of board bounds)

How to Handle:

Throw an IllegalArgumentException or return an error string like 'Invalid Move' since the board is only 3x3.

A move is placed on an already occupied cell

How to Handle:

Throw an IllegalArgumentException or return an error string, indicating invalid move as it violates the rules.

Moves do not alternate between players (e.g., player A moves twice in a row)

How to Handle:

Maintain player turn information to ensure correct alternation and return an error if it's violated.

Game ends before all 9 moves are made with no winner

How to Handle:

After all moves are processed and no winner is found, return 'Draw'.

Input contains only moves by player A or player B

How to Handle:

The algorithm should check for alternating moves and return an error if moves are not alternating.

A player wins before all possible moves are made

How to Handle:

The algorithm should detect the win and return 'A' or 'B' immediately.

The input contains negative values or non-integer values

How to Handle:

The algorithm should validate the input and throw an exception, or return an appropriate error string to indicate invalid input.