Valid Tic Tac Toe State - Leetcode Solution

The Valid Tic Tac Toe State problem on LeetCode is stated as follows:

A Tic Tac Toe board is given 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.

The board is a 3x3 array, and consists of the characters 'X', 'O', and ' '. The ' ' character represents an empty cell.

The rules of tic-tac-toe are as follows:

Players take turns placing characters into empty cells. The first player always places 'X' characters, while the second player always places 'O' characters. 'X' and 'O' characters are always placed into empty cells, never filled cells. A player wins when there are three of their characters in a row horizontally, vertically, or diagonally. The game ends when all cells are filled, or when one player wins the game. If the game is over and no player has won, it is called a draw.

To solve this problem we need to check if the given board is a valid Tic Tac Toe state that can be reached during the course of a valid Tic Tac Toe game. In order to check the validity, we need to do the following steps:

Step 1: Count the number of 'X' and 'O' characters on the board. Also, count the number of empty cells.

Step 2: Check if the number of 'X' is equal to the number of 'O', or the number of 'X' is exactly one more than the number of 'O'. If this condition is not satisfied, then the board is invalid because either there are too many 'X's or too many 'O's.

Step 3: Check if 'X' or 'O' has won the game. If both 'X' and 'O' have won, or if neither has won and there are empty cells, then the board is invalid.

Step 4: Check if 'X' has won the game. If 'X' has won, then the board is invalid if there are more 'O's than 'X's on the board, because 'X' always takes the first move, so it cannot have more 'O's.

Step 5: Check if 'O' has won the game. If 'O' has won, then the board is invalid if the number of 'X's and 'O's on the board is equal, because 'O' always takes the second move, so it cannot have the same number of 'X's and 'O's.

Step 6: If all the above conditions are satisfied, then the board is valid.

The Python implementation of the above steps is given below:

def validTicTacToe(board: List[str]) -> bool:

def countChars():
    xs, os, es = 0, 0, 0 # count of 'X', 'O', and empty cells (' ')
    for i in range(3):
        for j in range(3):
            if board[i][j] == 'X':
                xs += 1
            elif board[i][j] == 'O':
                os += 1
            else:
                es += 1
    return xs, os, es

def checkWin(ch):
    for i in range(3):
        if all(board[i][j] == ch for j in range(3)):
            return True
    for j in range(3):
        if all(board[i][j] == ch for i in range(3)):
            return True
    if all(board[i][i] == ch for i in range(3)):
        return True
    if all(board[i][2-i] == ch for i in range(3)):
        return True
    return False

xs, os, es = countChars()
if xs < os or xs > os + 1: # more X's or O's
    return False
if checkWin('X') and checkWin('O'): # both X and O have won (invalid)
    return False
if checkWin('X') and xs != os + 1: # X won but more O's
    return False
if checkWin('O') and xs != os: # O won but same number of X's and O's
    return False
return True

The countChars function counts the number of 'X', 'O', and empty cells on the board. The checkWin function checks if the given character has won the game.

The main function first counts the number of 'X', 'O', and empty cells on the board. Then it checks if the number of 'X' and 'O' is valid. If not, it returns False. If the number of 'X' and 'O' is valid, it checks if 'X' and 'O' have won the game or not. If both have won or neither has won and there are empty cells, it returns False. If 'X' has won and there are more 'O's on the board, or 'O' has won and the number of 'X's and 'O's is equal, then it returns False. If all the above conditions are satisfied, it returns True, which means the board is valid.

The time complexity of this algorithm is O(1), because we scan the board only once to count the number of 'X', 'O', and empty cells, and then we check for validity conditions. The space complexity is O(1), because we use only a constant amount of extra space to store the count of 'X', 'O', and empty cells.

1