Valid Tic-Tac-Toe State

Medium

Asked by:

20 views

Topics:

ArraysStrings

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.

The board is a 3 x 3 array that consists of characters ' ', 'X', and 'O'. The ' ' character represents an empty square.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares ' '.
The first player always places 'X' characters, while the second player always places 'O' characters.
'X' and 'O' characters are always placed into empty squares, never 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.

Example 1:

Input: board = ["O  ","   ","   "]
Output: false
Explanation: The first player always plays "X".

Example 2:

Input: board = ["XOX"," X ","   "]
Output: false
Explanation: Players take turns making moves.

Example 3:

Input: board = ["XOX","O O","XOX"]
Output: true

Constraints:

board.length == 3
board[i].length == 3
board[i][j] is either 'X', 'O', or ' '.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The input is a list of moves in a Tic-Tac-Toe game. Is the input guaranteed to represent a complete or potentially incomplete game, or could it be an arbitrary board state?
The board will contain 'X's and 'O's. Can I assume that the characters will *only* be 'X' and 'O', and potentially empty spaces (' ')?
Is the input guaranteed to be a valid sequence of moves, respecting the rules of Tic-Tac-Toe (e.g., X always goes first, and X and O alternate turns)? Or do I need to handle illegal sequences?
Are there any constraints on the length of the input list (number of moves)? The board is 3x3, so can I assume a maximum of 9 moves?
If the board state is valid but the game is a draw (no winner), should I return true or false?

Brute Force Solution

Approach

The brute force approach to validating a Tic-Tac-Toe board means we check every possible condition that makes a board valid or invalid. We will exhaustively look at all the possibilities for wins and number of moves, marking the board as valid only if it satisfies all criteria.

Here's how the algorithm would work step-by-step:

First, count how many 'X's and 'O's are on the board.
Check if the number of 'X's and 'O's make sense. 'X' should have the same number of pieces or one more than 'O', otherwise the game state is invalid.
Next, check for winning rows, columns, and diagonals for 'X'.
Then, do the same checking for winning rows, columns, and diagonals for 'O'.
Consider all win conditions. If 'X' wins, there cannot be more 'O's than 'X's. If 'O' wins, 'X' and 'O' must have the same number of pieces. If both win, the game state is invalid. If neither wins, we have to consider the count of marks still.
If no one won, consider the board valid only if the 'X' count equals the 'O' count or is only one greater than the 'O' count, meaning that 'X' made the last move.
If any of these checks fail, the board state is invalid. Otherwise, if it passes all checks, the board state is valid.

Code Implementation

def valid_tic_tac_toe_state(board):
    number_of_x = 0
    number_of_o = 0
    for row in board:
        for cell in row:
            if cell == 'X':
                number_of_x += 1
            elif cell == 'O':
                number_of_o += 1

    if number_of_o > number_of_x or number_of_x - number_of_o > 1:
        return False

    x_wins = check_win(board, 'X')
    o_wins = check_win(board, 'O')

    # If both win, the game state is invalid
    if x_wins and o_wins:
        return False

    if x_wins:
        # If 'X' wins, there cannot be more 'O's than 'X's
        if number_of_o > number_of_x:
            return False
    if o_wins:
        # If 'O' wins, 'X' and 'O' must have the same number of pieces
        if number_of_x != number_of_o:
            return False

    #If no one won, consider the count of marks
    if not x_wins and not o_wins:
        if number_of_x == number_of_o or number_of_x == number_of_o + 1:
            return True
        else:
            return False

    return True

def check_win(board, player):
    # Check rows
    for row in board:
        if all(cell == player for cell in row):
            return True

    # Check columns
    for column in range(3):
        if all(board[row][column] == player for row in range(3)):
            return True

    # Check diagonals
    if (board[0][0] == player and board[1][1] == player and board[2][2] == player):
        return True
    if (board[0][2] == player and board[1][1] == player and board[2][0] == player):
        return True

    return False

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through a fixed-size 3x3 Tic-Tac-Toe board. Counting 'X's and 'O's requires examining at most 9 cells. Checking rows, columns, and diagonals for wins involves a constant number of comparisons (8 win conditions). Therefore, the number of operations does not depend on a variable input size and remains constant. The time complexity is thus O(1).

Space Complexity

O(1) – The algorithm uses a few integer variables to store the counts of 'X' and 'O', as well as boolean variables to indicate if 'X' or 'O' has won. No auxiliary data structures are used that scale with the input board size. Thus, the space required is constant regardless of the Tic-Tac-Toe board (which is a fixed 3x3 size), resulting in O(1) space complexity.

Optimal Solution

Approach

To determine if a Tic-Tac-Toe board is valid, we need to check if the number of 'X's and 'O's are within the allowed range and if there is a valid winner. The key is to efficiently count the marks and check for winning conditions without overcomplicating the logic.

Here's how the algorithm would work step-by-step:

First, count how many 'X's and 'O's are on the board.
Check that the difference between the number of 'X's and 'O's is either 0 or 1. If it is any other value, the board is invalid.
Next, check if either 'X' or 'O' has won the game. To do this, look for three in a row vertically, horizontally, and diagonally for each mark.
If 'X' wins, make sure 'O' has not won. If 'O' wins, make sure 'X' has not won. If both have won, the board is invalid.
If 'X' wins, the number of 'X's must be one more than the number of 'O's. If 'O' wins, the number of 'X's and 'O's must be equal. If this condition isn't met, the board is invalid.
If no one has won and the board is valid so far, simply return that it is a valid board. This ensures that all constraints are satisfied.

Code Implementation

def valid_tic_tac_toe_state(board):
    number_of_x = 0
    number_of_o = 0

    for row in board:
        for cell in row:
            if cell == 'X':
                number_of_x += 1
            elif cell == 'O':
                number_of_o += 1

    # Check if the difference between Xs and Os is valid.
    if not (number_of_x == number_of_o or number_of_x == number_of_o + 1):
        return False

    def check_win(mark):
        # Check rows
        for row in board:
            if all(cell == mark for cell in row):
                return True
        # Check columns
        for column in range(3):
            if all(board[row][column] == mark for row in range(3)):
                return True
        # Check diagonals
        if (board[0][0] == mark and board[1][1] == mark and board[2][2] == mark):
            return True
        if (board[0][2] == mark and board[1][1] == mark and board[2][0] == mark):
            return True
        return False

    x_wins = check_win('X')
    o_wins = check_win('O')

    # If both X and O win, the board is invalid.
    if x_wins and o_wins:
        return False

    # Validate winner based on X and O counts.
    if x_wins:
        if number_of_x != number_of_o + 1:
            return False

    if o_wins:
        if number_of_x != number_of_o:
            return False

    return True

Big(O) Analysis

Time Complexity

O(1) – The algorithm examines a fixed-size 3x3 Tic-Tac-Toe board. Counting 'X's and 'O's iterates through the 9 cells, a constant number of operations. Checking for wins involves checking a fixed number of rows, columns, and diagonals (8 total), independent of any input size 'n'. Therefore, the total number of operations is bounded by a constant, resulting in O(1) time complexity.

Space Complexity

O(1) – The algorithm uses a fixed number of integer variables to count the number of 'X's and 'O's, and boolean variables to track whether 'X' or 'O' has won. The board size is constant (3x3), so the number of checks for winning conditions is also constant. Therefore, the auxiliary space required does not depend on the input size, resulting in constant space complexity.

Edge Cases

Case	How to Handle
Null or empty board	Return true (or false, depending on specified expected behavior for invalid input) immediately since it's not a valid game state.
Board with invalid characters (not 'X', 'O', or ' ')	Return false, as the board contains illegal characters, violating Tic-Tac-Toe rules.
More 'O's than 'X's	Return false, since 'X' always plays first or the same number as 'O'.
Too many 'X's or 'O's relative to board size	Return false, as it would be impossible to make that many moves in a valid Tic-Tac-Toe game on the given board.
Both 'X' and 'O' have won	Return false, because in a standard Tic-Tac-Toe game, only one player can win.
'X' won, but it's 'O's turn	Return false, as the game should have ended when 'X' won.
'O' won, but it's 'X's turn and the number of 'X's and 'O's are equal	Return false because 'X' made the last move and cannot be behind.
Board is full, but no one has won	Return true, which is a valid tie game state.

Null or empty board

How to Handle:

Return true (or false, depending on specified expected behavior for invalid input) immediately since it's not a valid game state.

Board with invalid characters (not 'X', 'O', or ' ')

How to Handle:

Return false, as the board contains illegal characters, violating Tic-Tac-Toe rules.

More 'O's than 'X's

How to Handle:

Return false, since 'X' always plays first or the same number as 'O'.

Too many 'X's or 'O's relative to board size

How to Handle:

Return false, as it would be impossible to make that many moves in a valid Tic-Tac-Toe game on the given board.

Both 'X' and 'O' have won

How to Handle:

Return false, because in a standard Tic-Tac-Toe game, only one player can win.

'X' won, but it's 'O's turn

How to Handle:

Return false, as the game should have ended when 'X' won.

'O' won, but it's 'X's turn and the number of 'X's and 'O's are equal

How to Handle:

Return false because 'X' made the last move and cannot be behind.

Board is full, but no one has won

How to Handle:

Return true, which is a valid tie game state.