algoadvance

The objective is to determine if a given Tic-Tac-Toe board state is valid. A valid Tic-Tac-Toe board state requires that:

1. The number of ‘X’ and ‘O’ pieces is such that ‘X’ can either be equal to or exactly one more than the number of ‘O’ pieces.
2. Neither player has multiple winning lines simultaneously: it’s either one win or none.

More specifically:

• ‘X’ always goes first, and the players alternate turns.
• ‘X’ cannot have more pieces than ‘O’ + 1.
• ‘O’ cannot have more pieces than ‘X’.
• A player cannot continue playing after the game is already won.

A winning line consists of three of the same pieces in a row, column, or diagonal.

Input: A single list of strings representing the Tic-Tac-Toe board state. Each string represents a row on the board.

Output: A boolean value indicating whether the given Tic-Tac-Toe board is valid.

Example:

board = ["O  ", "   ", "   "]
# False because the first move should be 'X'

Clarifying Questions

1. Can the board contain characters other than ‘X’, ‘O’, and space (‘ ‘)?
   • No, the board only includes ‘X’, ‘O’, and space.
2. Is the input always guaranteed to be a valid 3x3 board?
   • Yes, the input is always a valid 3x3 board.
3. Do we need to check for both players winning simultaneously?
   • Yes, that scenario should be considered invalid.

Strategy

1. Count the number of ‘X’ and ‘O’ on the board.
2. Validate the counts:
   • ‘X’ count == ‘O’ count or ‘X’ count == ‘O’ count + 1.
3. Define a helper function to check if a player has won.
4. Validate the winning state:
   • If ‘X’ wins, ‘X’ count should be ‘O’ count + 1.
   • If ‘O’ wins, ‘X’ count should be ‘O’ count.
   • Both ‘X’ and ‘O’ cannot win simultaneously.

Time Complexity

• Counting ‘X’ and ‘O’: O(1)
• Checking wins is O(1) as it involves only a fixed number of checks for rows, columns, and diagonals in a 3x3 matrix.
• Overall time complexity: O(1)

Code

def validTicTacToe(board):
    # Counting the number of X's and O's
    x_count = sum(row.count('X') for row in board)
    o_count = sum(row.count('O') for row in board)
    
    # Checking if the count of X's and O's is valid
    if not (x_count == o_count or x_count == o_count + 1):
        return False
    
    # Function to check whether a particular player has won
    def is_winner(player):
        # All possible winning directions
        win_states = [
            [board[0][0], board[0][1], board[0][2]],
            [board[1][0], board[1][1], board[1][2]],
            [board[2][0], board[2][1], board[2][2]],

            [board[0][0], board[1][0], board[2][0]],
            [board[0][1], board[1][1], board[2][1]],
            [board[0][2], board[1][2], board[2][2]],
            
            [board[0][0], board[1][1], board[2][2]],
            [board[0][2], board[1][1], board[2][0]]
        ]
        return [player, player, player] in win_states
    
    x_wins = is_winner('X')
    o_wins = is_winner('O')
    
    # Both players cannot win the game simultaneously
    if x_wins and o_wins:
        return False
    
    # If X wins, there must be one more X than O
    if x_wins and x_count != o_count + 1:
        return False
    
    # If O wins, there must be the same number of X and O
    if o_wins and x_count != o_count:
        return False
    
    return True

# Example usage:
board = ["XOX", "O O", "XOX"]
print(validTicTacToe(board)) # Output: False (both cannot win simultaneously)

This code checks for valid counts of ‘X’ and ‘O’, ensures that only one player can win, and ensures the conditions for a valid Tic-Tac-Toe game state are maintained.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?