We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Tic-Tac-Toe State

Difficulty: Medium

Problem Description

Given a Tic-Tac-Toe board as a string array board, return true if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

Key Insights

  • Players take turns placing characters into empty squares.
  • The first player always places X characters, while the second player places O characters.
  • The count of X should either be equal to or one more than the count of O.
  • If X wins, the count of X must be one more than O.
  • If O wins, the count of X must be equal to the count of O.
  • The game cannot continue if there's a winner.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

To determine if the given Tic-Tac-Toe board is valid, we will:

  1. Count the occurrences of X and O.
  2. Check all possible winning combinations for both players.
  3. Validate the counts based on the game rules and winning conditions.

We will use a simple array to represent the board and check rows, columns, and diagonals for winning conditions. The algorithm will ensure that the counts of X and O are consistent with the rules of Tic-Tac-Toe.

Code Solutions

def validTicTacToe(board):
    x_count = sum(row.count('X') for row in board)
    o_count = sum(row.count('O') for row in board)

    # Check for valid counts of X and O
    if o_count > x_count or x_count > o_count + 1:
        return False

    # Winning combinations
    wins = [
        [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]],
    ]

    x_win = any(win == ['X', 'X', 'X'] for win in wins)
    o_win = any(win == ['O', 'O', 'O'] for win in wins)

    # Check winning conditions
    if x_win and o_win:
        return False
    if x_win and x_count != o_count + 1:
        return False
    if o_win and x_count != o_count:
        return False

    return True
← Back to All Questions