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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Tic-Tac-Toe State

Number: 810

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given a 3x3 Tic-Tac-Toe board represented as a string array, determine if the board state is valid—that is, whether it is possible to reach such a state during the course of a valid Tic-Tac-Toe game. The board contains characters 'X', 'O', and ' ' (empty spaces). The game rules impose that the first player (X) always starts, players must alternate moves, and the game stops once one of the players wins (or when the board is full). This means the counts of X’s and O’s and any winning configuration must satisfy specific conditions.

Key Insights

  • Count the occurrences of 'X' and 'O'. Valid states require that either countX == countO or countX == countO + 1.
  • Check for winning configurations (three in a row) for both X and O.
  • If X wins, then countX must equal countO + 1.
  • If O wins, then countX must equal countO.
  • Both players cannot win simultaneously.
  • The board state must adhere to the turn order and termination conditions.

Space and Time Complexity

Time Complexity: O(1) - The board size is fixed (3x3), so iterations are constant. Space Complexity: O(1) - Only a few counters and helper functions are used regardless of input size.

Solution

We validate the board by:

  1. Counting 'X' and 'O' on the board.
  2. Verifying that X has either the same number of moves as O or one more move.
  3. Checking if there is a winning row, column, or diagonal for X or O.
  4. Ensuring that if one player wins, the counts correspond to the expected turn (if X wins, then countX must be one more than countO; if O wins, counts must be equal) and both winning simultaneously is invalid.

To implement this, we use helper functions to detect wins and straightforward counting. The use of fixed iterations (3 rows, 3 columns, 2 diagonals) ensures constant time, making the overall solution efficient.

Code Solutions

# Python solution with comments
class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        # Count the number of X's and O's on the board
        countX = sum(row.count('X') for row in board)
        countO = sum(row.count('O') for row in board)
        
        # The game starts with X, so there must be equal number of moves or one extra X
        if not (countX == countO or countX == countO + 1):
            return False

        # Define a helper function to check if a player has won
        def win(player: str) -> bool:
            # Check all rows for win
            for i in range(3):
                if board[i] == player * 3:
                    return True
            # Check all columns for win
            for j in range(3):
                if board[0][j] == board[1][j] == board[2][j] == player:
                    return True
            # Check diagonals for win
            if board[0][0] == board[1][1] == board[2][2] == player:
                return True
            if board[0][2] == board[1][1] == board[2][0] == player:
                return True
            return False

        # Determine winning status for both players
        winX = win('X')
        winO = win('O')
        
        # Both players cannot win at the same time
        if winX and winO:
            return False
        # If X wins, X must have one more move than O
        if winX and countX != countO + 1:
            return False
        # If O wins, both must have equal number of moves
        if winO and countX != countO:
            return False
        return True
← Back to All Questions