Find Winner On A Tic Tac Toe Game - Leetcode Solution

Problem Statement:

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The game starts with player A placing their symbol on an empty square. Then player B places their symbol on another empty square, and the two players alternate turns. The first player to get three of their symbols in a row (horizontally, vertically, or diagonally) is the winner. If the board is full and no one wins, the game is a draw.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective symbol A or B, return the winner of the game if it exists (A or B), in case the game ends up in a draw return "Draw", if there are still movements to play return "Pending".

Solution:

To solve this problem, we need to simulate the game of tic-tac-toe using the provided moves array. We will store the current state of the board in a 3x3 matrix. Initially, the elements in the matrix will be empty.

We will traverse through the moves array and do the following:

• For player A, we will mark the corresponding cell in the matrix with "X".
• For player B, we will mark the corresponding cell in the matrix with "O".
• After each move, we will check if any of the rows, columns or diagonals have three consecutive X's or O's. If that is the case, we will return the winner.
• If all the moves are finished and nobody wins, we will return "Draw".
• If there are still moves to be played, we will return "Pending".

Code:

To implement the above approach, we can create a function findWinner that takes in the array of moves and returns the winner of the game. Here is the code:

def findWinner(moves):
    # Initialize the board
    board = [[0] * 3 for _ in range(3)]

    # Update the board based on the moves
    for i, move in enumerate(moves):
        if i % 2 == 0:
            # Player A's move
            board[move[0]][move[1]] = "X"
            if checkWinner(board, "X"):
                return "A"
        else:
            # Player B's move
            board[move[0]][move[1]] = "O"
            if checkWinner(board, "O"):
                return "B"
            
    # If all moves are finished and nobody wins, return Draw
    if len(moves) == 9:
        return "Draw"
    
    # If there are still moves to be played, return Pending
    return "Pending"
    
def checkWinner(board, player):
    # Check rows
    for i in range(3):
        if board[i][0] == board[i][1] == board[i][2] == player:
            return True

    # Check columns
    for j in range(3):
        if board[0][j] == board[1][j] == board[2][j] == player:
            return True

    # Check diagonals
    if board[0][0] == board[1][1] == board[2][2] == player:
        return True
    if board[0][2] == board[1][1] == board[2][0] == player:
        return True

    return False

The checkWinner function checks if the player has won by checking if any of the rows, columns or diagonals have three consecutive X's or O's. We pass the board and the player symbol to this function.

The findWinner function initializes the board and updates it based on the moves provided. It then checks for a winner after each move and returns the winner if any. If all the moves are finished and nobody wins, it returns "Draw". If there are still moves to be played, it returns "Pending".

Time Complexity:

The time complexity of the solution is O(1) as we are iterating through a fixed 3x3 matrix and the maximum number of moves that can be made is 9.

Space Complexity:

The space complexity of the solution is O(1) as we are only storing a fixed 3x3 matrix and a few variables to keep track of the moves and winner.

1