Domain 2MediumMEDIUM

Valid Tic-Tac-Toe State

LeetCode problem 794: Valid Tic-Tac-Toe State (medium).

Domain: medium•Updated: 2026-09-01
#Math#Recursion

Problem Breakdown

We are given a 3x3 Tic-Tac-Toe board represented as an array of strings containing " ", "X", and "O". We need to determine if it is possible for the game to have reached this exact state following standard rules:

  1. Turn Order: X always goes first, followed by alternating turns (X, then O).
  2. Game Termination: The game stops immediately when a player wins (3 in a row/column/diagonal) or the board is full. No further moves are allowed after this point.

Implicit Constraints & Edge Cases:

  • Counts: Since X starts, there can be at most one more "X" than "O". Specifically: count("X") == count("O") (if it’s O’s turn or game over) OR count("X") == count("O") + 1 (if it was X’s move).
  • Win States: It is impossible for both players to have a winning line simultaneously because the game ends as soon as one player wins. If we see two winners, the state is invalid unless that configuration could theoretically exist without violating turn order (which implies illegal moves continued after win), so generally False.
  • Input Validity: The input characters are guaranteed to be valid (" ", "X", "O"). We don’t need to validate character types, only the state logic.

Intuition

A brute-force approach would attempt to replay every possible game path from an empty board until we reach a match or determine impossibility. This involves recursion/backtracking with complexity roughly proportional to 393^9 (branching factor 3 per cell), which is computationally expensive and unnecessary given the fixed grid size.

Key Insight: We don’t need to simulate moves; we just need to validate if the current state satisfies the necessary conditions derived from game rules:

  1. Count Constraint: The number of Xs must be equal to or exactly one greater than the number of Os. If count("O") > count("X"), it’s impossible because O cannot move before X, and they alternate strictly.
  2. Win Consistency:
    • If X has won, X must have just moved (so count("X") == count("O") + 1). Additionally, O cannot have a winning line because the game would have ended before O could complete their win.
    • If O has won, it implies X did not move after that turn, so counts must be equal (count("X") == count("O")). Also, X cannot have a winning line for the same reason as above.

Approach

  1. Count Characters: Iterate through the board to calculate total occurrences of "X" and "O". Let these be cXc_X and cOc_O. Validate that 0≤cX−cO≤10 \le c_X - c_O \le 1. If not, return False immediately.
  2. Check Win States: Implement a helper function or logic to check if there is any winning line for "X" (win_xwin\_x) and/or "O" (win_owin\_o). A win exists if three identical characters occupy a row, column, or diagonal.
  3. Apply Logic Rules:
    • If both win_xwin\_x and win_owin\_o are true: Return False (game would have ended earlier).
    • If only win_xwin\_x is true: Check if cX==cO+1c_X == c_O + 1. If not, return False. Otherwise valid.
    • If only win_owin\_o is true: Check if cX==cOc_X == c_O. If not, return False. Otherwise valid.
    • If neither won: The state must be a draw or in-progress. Since counts are already validated (∣cX−cO∣≤1|c_X - c_O| \le 1), this case returns True (provided the board isn’t full with mismatched turns which is covered by count check).

Complexity Analysis

  • Time Complexity: O(1)O(1). Although we iterate over cells, a Tic-Tac-Toe board has fixed dimensions (3×3=93 \times 3 = 9 cells). Therefore, operations are constant time relative to input size. If generalized for an N×NN \times N grid, it would be O(N2)O(N^2) where N=3N=3.
  • Space Complexity: O(1)O(1). We only use a few integer variables and boolean flags regardless of board content (excluding recursion stack if we used backtracking).

Solution

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        # Helper to count occurrences on the board
        x_count = 0
        o_count = 0
        
        for row in board:
            x_count += row.count('X')
            o_count += row.count('O')
            
        # Constraint 1: X goes first, so counts must be equal or X has one more.
        if not (x_count == o_count + 1 or x_count == o_count):
            return False
            
        def check_win(player_char):
            """Checks if the given player has a winning line."""
            # Check rows and columns
            for i in range(3):
                if board[i][0] == player_char and board[i][1] == player_char and board[i][2] == player_char: return True
                if board[0][i] == player_char and board[1][i] == player_char and board[2][i] == player_char: return True
            
            # Check diagonals
            if board[0][0] == player_char and board[1][1] == player_char and board[2][2] == player_char: return True
            if board[0][2] == player_char and board[1][1] == player_char and board[2][0] == player_char: return True
            
            return False

        x_wins = check_win('X')
        o_wins = check_win('O')
        
        # Constraint 2 & 3: Game ends immediately upon a win. 
        # If X wins, O cannot have won (and counts must reflect X's last move).
        if x_wins and o_wins: return False
        
        if x_wins:
            # If X just moved to win, count(X) must be greater than count(O)
            return x_count == o_count + 1
            
        if o_wins:
            # If O won, it was their turn (counts equal), and game ended. 
            # Note: Since we checked both wins above, this implies only O has a win line here?
            # Actually logic handles 'if not x_wins' implicitly in flow below but explicit check is safer.
            return x_count == o_count
            
        # If neither won, just need to satisfy count constraint (already done at top)
        return True

Edge Cases Handled

  • Both Players Win: The code explicitly checks if x_wins and o_wins: return False. This handles the case where lines exist for both players simultaneously. Since turns alternate, one player must have moved after the other won to create this state, which is illegal.
  • X Wins with Equal Counts: If X wins but cX==cOc_X == c_O, it implies O made a move after X completed their winning line (impossible). The code enforces return x_count == o_count + 1 in the x_wins branch, catching this.
  • O Wins with Unequal Counts: If O wins but cX>cOc_X > c_O, it implies X moved after O won or started incorrectly. The logic ensures if only O wins (or neither), counts must be equal (return x_count == o_count).
  • Empty Board / Initial State: While not explicitly an input case, the count check handles a board with 0 moves (cX=0,cO=0c_X=0, c_O=0) correctly as valid.