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 ith 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" Explanation: A wins, they always play first.

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

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.

def tictactoe(moves):
    """Determines the winner of a Tic-Tac-Toe game given a list of moves.

    Args:
        moves (list of lists): A list of moves, where each move is a list [row, col].

    Returns:
        str: The winner of the game ("A" or "B"), "Draw", or "Pending".
    """
    board = [[' ' for _ in range(3)] for _ in range(3)]
    player = 'A'

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

    # Check rows
    for row in range(3):
        if board[row][0] == board[row][1] == board[row][2] != ' ':
            return 'A' if board[row][0] == 'X' else 'B'

    # Check columns
    for col in range(3):
        if board[0][col] == board[1][col] == board[2][col] != ' ':
            return 'A' if board[0][col] == 'X' else 'B'

    # Check diagonals
    if board[0][0] == board[1][1] == board[2][2] != ' ':
        return 'A' if board[0][0] == 'X' else 'B'
    if board[0][2] == board[1][1] == board[2][0] != ' ':
        return 'A' if board[0][2] == 'X' else 'B'

    # Check for draw or pending
    if len(moves) == 9:
        return "Draw"
    else:
        return "Pending"

# Example Usage
moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]]
print(f"Result for moves1: {tictactoe(moves1)}") # Output: A

moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
print(f"Result for moves2: {tictactoe(moves2)}") # Output: B

moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
print(f"Result for moves3: {tictactoe(moves3)}") # Output: Draw

moves4 = [[0,0],[1,1]]
print(f"Result for moves4: {tictactoe(moves4)}") # Output: Pending

Explanation:

1. Initialize the board: A 3x3 board is created, initialized with empty spaces.
2. Simulate moves: Iterate through the moves list, placing 'X' for player A and 'O' for player B.
3. Check for a winner: After each move, check rows, columns, and diagonals for three in a row of the same symbol.
4. Determine draw or pending: If all squares are filled and no winner is found, it's a draw. If there are moves left, the game is pending.

Big O Runtime Analysis:

The runtime complexity is O(1) because the board size is constant (3x3), and the maximum number of moves is 9. The algorithm iterates through the moves list (at most 9 elements) and performs a constant amount of work for each move (checking rows, columns, and diagonals, which are fixed sizes). Therefore, the dominant operations do not depend on the input size in a way that would increase the complexity beyond constant time.

Big O Space Usage Analysis:

The space complexity is O(1) because the size of the board is constant (3x3). The algorithm uses a fixed amount of space to store the board and a few variables, regardless of the number of moves. The space used does not scale with the input size, making it constant space complexity.

Edge Cases:

1. Invalid moves: The problem statement assumes that the moves are valid. We could add a check to ensure that a player isn't playing on an already filled square.
2. Premature game end: The provided code handles cases where a player wins before all 9 moves are made.
3. Empty input: If the moves list is empty, the function will correctly return "Pending" as the board is empty and the game hasn't started.
4. More than 9 moves: The problem statement says that there are no repeated elements on moves, so we can assume there will never be more than 9 moves.