Find Winner on a Tic Tac Toe Game Interview Question for Google

You are given a 2D array moves representing moves in a Tic-Tac-Toe game. The game is played on a 3x3 grid. Players A and B take turns, with A placing 'X' and B placing 'O'.

Each element moves[i] = [row_i, col_i] represents the row and column where the i-th move is played. The game ends when:

A player has three of their symbols in a row, column, or diagonal.
All squares are filled (a draw).

Your task is to determine the winner of the game (A or B), if there is one. If the game is a draw, return "Draw". If there are moves left to play, return "Pending".

Assumptions:

moves is a valid sequence of moves (no out-of-bounds moves, no placing on occupied squares).
The grid is initially empty.
A always goes first.

Example 1:

moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]

Output: "A"

Example 2:

moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]

Output: "B"

Example 3:

moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]

Output: "Draw"

Example 4:

moves = [[0,0],[1,1]]

Output: "Pending"

Naive Approach

The most straightforward approach is to simulate the Tic-Tac-Toe game based on the given moves. We can create a 3x3 board and update it with 'X' and 'O' alternatively. After each move, we check if the current player has won by examining all rows, columns, and diagonals. If no one wins and all moves are made, it's a draw. If there are moves left, the game is pending.

Code (Python):

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

    for move in moves:
        row, col = move
        board[row][col] = player

        # Check if current player wins
        if check_win(board, player):
            return player

        player = 'O' if player == 'X' else 'X'

    # Check if draw or pending
    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

Big(O) Analysis:

Time Complexity: O(m), where m is the number of moves. In each move, we check for a win which takes O(1) time as the board size is constant (3x3).
Space Complexity: O(1), as the board size is fixed (3x3).

Optimal Approach

Instead of checking all rows, columns, and diagonals after each move, we can optimize the win check. For each move, we only need to check the row, column, and diagonals that the move belongs to. We can maintain separate counters for rows, columns, and diagonals for each player. This avoids iterating through the entire board after each move.

Code (Python):

def tic_tac_toe_optimal(moves):
    rows = {[x: 0 for x in ["A", "B"]] for _ in range(3)}
    cols = {[x: 0 for x in ["A", "B"]] for _ in range(3)}
    diag = {"A": 0, "B": 0}
    anti_diag = {"A": 0, "B": 0}

    player = "A"
    for i, move in enumerate(moves):
        row, col = move

        if i % 2 == 0:
            curr_player = "A"
        else:
            curr_player = "B"

        rows[row][curr_player] += 1
        cols[col][curr_player] += 1

        if row == col:
            diag[curr_player] += 1

        if row + col == 2:
            anti_diag[curr_player] += 1

        if (rows[row][curr_player] == 3 or
            cols[col][curr_player] == 3 or
            diag[curr_player] == 3 or
            anti_diag[curr_player] == 3):
            return curr_player

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

Big(O) Analysis:

Time Complexity: O(m), where m is the number of moves. Each move only requires updating a few counters, which is O(1).
Space Complexity: O(1), since we are using a fixed number of counters regardless of the input size.

Edge Cases

Empty input moves: return "Pending"
One player wins early: return the winning player
Full board with no winner: return "Draw"
Invalid moves (out of bound or on a filled cell) is assumed to be handled by the problem constraints.

Find Winner on a Tic Tac Toe Game

Solution

Naive Approach

Optimal Approach

Edge Cases