Find Winner on a Tic Tac Toe Game

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] = [rowi, coli] indicates that the i<sup>th</sup> move will be played on grid[rowi][coli]. 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.

For example:

moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] Output: "A"

moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] Output: "B"

moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] Output: "Draw"

Tic-Tac-Toe Winner

Here's a solution to determine the winner of a Tic-Tac-Toe game given a sequence of moves.

Naive Approach

The most straightforward approach is to simulate the game move by move. After each move, we check if the current player has won by examining all possible winning conditions (rows, columns, and diagonals). If no winner is found and all moves have been made, we declare a draw. If moves are still pending, we return "Pending".

def tic_tac_toe_winner_naive(moves):
    board = [[' ' for _ in range(3)] for _ in range(3)]
    player = 'A'

    for move in moves:
        row, col = move
        if player == 'A':
            board[row][col] = 'X'
        else:
            board[row][col] = 'O'

        # Check for win
        if check_win(board, 'X' if player == 'A' else 'O'):
            return player

        player = 'B' if player == 'A' else 'A'

    if len(moves) == 9:
        return "Draw"
    else:
        return "Pending"


def check_win(board, player):
    # Check rows
    for row in board:
        if all(cell == player for cell in row):
            return True

    # Check columns
    for col in range(3):
        if all(board[row][col] == player for row in range(3)):
            return True

    # Check diagonals
    if all(board[i][i] == player for i in range(3)):
        return True
    if all(board[i][2 - i] == player for i in range(3)):
        return True

    return False

Optimal Approach

We can optimize the solution by keeping track of the number of 'X's and 'O's in each row, column, and diagonal. This allows us to check for a win in O(1) time after each move, rather than iterating through the entire board.

def tic_tac_toe_winner(moves):
    rows = [0] * 3
    cols = [0] * 3
    diag = 0
    anti_diag = 0
    player = 1  # 1 for A, -1 for B

    for row, col in moves:
        rows[row] += player
        cols[col] += player
        if row == col:
            diag += player
        if row + col == 2:
            anti_diag += player

        if abs(rows[row]) == 3 or abs(cols[col]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
            return "A" if player == 1 else "B"

        player *= -1

    if len(moves) == 9:
        return "Draw"
    else:
        return "Pending"

Big(O) Run-time Analysis

The optimal solution has a time complexity of O(N), where N is the number of moves. This is because we iterate through the moves list once, and each move takes constant time to process.

Big(O) Space Usage Analysis

The optimal solution has a space complexity of O(1) because we only use a fixed number of variables to store the counts of rows, columns, and diagonals, regardless of the number of moves.

Edge Cases

• Invalid Moves: The problem statement assumes that the moves are valid. If invalid moves are possible (e.g., a move on an already occupied square), we need to add a check to ensure the move is valid before processing it.
• Empty Moves List: If the moves list is empty, the game is pending.
• Early Win: The game might be won before all 9 moves are made. The solution correctly identifies the winner in such cases.
• Draw Condition: The solution correctly identifies a draw when all squares are filled and no player has won.