Problem Description

This problem asks you to validate whether a given Tic-Tac-Toe board configuration could be reached through a valid game sequence.

You're given a 3×3 board represented as a string array where:

• 'X' represents player 1's marks
• 'O' represents player 2's marks
• ' ' (space) represents empty squares

The rules of Tic-Tac-Toe that must be followed are:

1. Player 1 ('X') always goes first, followed by Player 2 ('O') taking turns
2. Players can only place marks in empty squares
3. The game ends when either:
   • A player gets three marks in a row (horizontally, vertically, or diagonally)
   • All squares are filled
4. No moves can be made after the game ends

Your task is to determine if the given board state is valid - meaning it could actually occur during a legitimate game following these rules.

For example, a board with 5 'X' marks and 2 'O' marks would be invalid since players alternate turns (so 'X' can have at most one more mark than 'O'). Similarly, if both players have winning positions simultaneously, that would be impossible in a real game since the game ends as soon as one player wins.

The solution needs to check several validity conditions:

• The count of 'X' marks should equal the count of 'O' marks, or be exactly one more (since 'X' goes first)
• If 'X' has won, they must have exactly one more mark than 'O' (the game ended on X's turn)
• If 'O' has won, they must have the same count as 'X' (the game ended on O's turn)
• Both players cannot have won simultaneously

Intuition

To determine if a board state is valid, we need to think about what makes a Tic-Tac-Toe game invalid. Since we're working backwards from a final board state, we need to verify that this state could have been reached through legal moves.

The key insight is that there are only a few ways a board can be invalid:

1. Turn count violation: Since 'X' always goes first and players alternate, the number of 'X' marks should either equal the number of 'O' marks (when 'O' just played) or be exactly one more (when 'X' just played). Any other difference means someone played out of turn.

2. Playing after winning: If a player has won, the game should have ended immediately. So we need to check:

   • If 'X' won, it must have been on 'X''s turn, meaning x_count = o_count + 1
   • If 'O' won, it must have been on 'O''s turn, meaning x_count = o_count
   • Both players cannot win (the game would have ended when the first player won)

The approach becomes clear: first count the marks for each player, then check if any player has won, and finally validate these results against the game rules.

For checking wins, we need to examine all possible winning configurations: 3 rows, 3 columns, and 2 diagonals. A player wins if they have all three positions in any of these lines.

The validation logic follows naturally:

• If the count difference is wrong (x != o and x - 1 != o), it's invalid
• If 'X' won but doesn't have exactly one more mark than 'O', it's invalid (game should have ended on X's turn)
• If 'O' won but doesn't have equal marks with 'X', it's invalid (game should have ended on O's turn)

This gives us a clean, systematic way to validate any board configuration by checking these necessary conditions.

Solution Approach

The solution implements the validation logic through a systematic check of game rules:

1. Win Detection Helper Function

First, we create a helper function win(x) that checks if player x (either 'X' or 'O') has won:

• Check all 3 rows: all(board[i][j] == x for j in range(3)) for each row i
• Check all 3 columns: all(board[j][i] == x for j in range(3)) for each column i
• Check main diagonal: all(board[i][i] == x for i in range(3))
• Check anti-diagonal: all(board[i][2 - i] == x for i in range(3))

The function returns True if any winning condition is met.

2. Count the Marks

Count the total number of 'X' and 'O' marks on the board:

x = sum(board[i][j] == 'X' for i in range(3) for j in range(3))
o = sum(board[i][j] == 'O' for i in range(3) for j in range(3))

This uses nested list comprehension to iterate through all 9 positions and count occurrences.

3. Validate Turn Count

Check if the difference in counts is valid:

if x != o and x - 1 != o:
    return False

Since 'X' goes first, valid states are:

• x == o: 'O' just played
• x == o + 1: 'X' just played

Any other difference means someone played out of turn.

4. Validate Win Conditions

Check if wins are consistent with turn counts:

if win('X') and x - 1 != o:
    return False

If 'X' won, the game ended on 'X''s turn, so x must be exactly o + 1.

return not (win('O') and x != o)

If 'O' won, the game ended on 'O''s turn, so x must equal o. The expression returns False if 'O' won but the counts don't match.

Time and Space Complexity:

• Time: O(1) - We check a fixed 3×3 board with constant operations
• Space: O(1) - Only using a few variables regardless of input

The solution elegantly handles all invalid cases through these conditional checks, ensuring the board represents a reachable game state.

Example Walkthrough

Let's walk through validating this board configuration:

["XOX",
 "O O",
 "XOX"]

Step 1: Count the marks

• Count X's: positions (0,0), (0,2), (2,0), (2,2) → x = 4
• Count O's: positions (0,1), (1,0), (1,2) → o = 3
• Difference check: x - o = 1 ✓ (valid since X goes first)

Step 2: Check if X has won

• Row 0: X-O-X (no)
• Row 1: O-' '-O (no)
• Row 2: X-O-X (no)
• Column 0: X-O-X (no)
• Column 1: O-' '-O (no)
• Column 2: X-O-X (no)
• Main diagonal: X-' '-X (no)
• Anti-diagonal: X-' '-X (no)
• Result: X has not won

Step 3: Check if O has won

• Using same checks: O has not won

Step 4: Apply validation rules

• Turn count valid? x = o + 1 ✓
• If X won, is x = o + 1? Not applicable (X didn't win)
• If O won, is x = o? Not applicable (O didn't win)

Result: Valid board ✓

Now let's try an invalid example:

["XXX",
 "OOO",
 "   "]

Step 1: Count the marks

• X count: 3, O count: 3

Step 2: Check wins

• X has won (top row: XXX)
• O has won (middle row: OOO)

Step 3: Validation fails Both players cannot win in a valid game since the game ends immediately when one player wins. This board is invalid ✗.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The time complexity is constant because:

• The board size is fixed at 3×3, so all loops iterate a constant number of times
• The win function checks 8 possible winning conditions (3 rows + 3 columns + 2 diagonals), each requiring at most 3 comparisons
• Counting 'X' and 'O' pieces requires iterating through 9 cells exactly once
• All operations are performed on a fixed-size board, making the total number of operations constant regardless of input

Space Complexity: O(1)

The space complexity is constant because:

• Only a fixed number of integer variables (x and o) are used to store counts
• The win function uses no additional data structures
• No recursive calls are made that would consume stack space
• The input board is not copied or modified, only read
• All operations use a constant amount of extra memory independent of the input size (which is already fixed)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting that Both Players Can't Win Simultaneously

One of the most common mistakes is not checking whether both players have winning positions on the board. In a valid Tic-Tac-Toe game, once a player wins, the game immediately ends - so it's impossible for both players to have three in a row.

Incorrect approach:

def validTicTacToe(self, board: List[str]) -> bool:
    # ... count X's and O's ...
  
    # Only checking individual win conditions separately
    if check_winner('X') and x_count - 1 != o_count:
        return False
    if check_winner('O') and x_count != o_count:
        return False
    return True

The problem: This code would incorrectly return True for a board where both X and O have winning positions, as long as the count conditions are met individually.

Correct solution:

def validTicTacToe(self, board: List[str]) -> bool:
    # ... count X's and O's ...
  
    x_wins = check_winner('X')
    o_wins = check_winner('O')
  
    # Both players cannot win
    if x_wins and o_wins:
        return False
  
    # Check win conditions with proper counts
    if x_wins and x_count - 1 != o_count:
        return False
    if o_wins and x_count != o_count:
        return False
  
    return True

2. Misunderstanding Turn Count Logic

Another frequent error is incorrectly validating the relationship between X and O counts. Remember that X always goes first, so the valid count differences are limited.

Incorrect approach:

# Wrong: allowing X to be ahead by more than 1
if x_count - o_count > 1:
    return False

# Wrong: allowing O to have more marks than X
if o_count > x_count:
    return False

The problem: The first check alone doesn't catch when O has more marks than X. The second check alone doesn't catch when X is too far ahead.

Correct solution:

# X can only be equal to O or exactly one ahead
if x_count != o_count and x_count - 1 != o_count:
    return False

This single condition handles both cases: it ensures O never has more marks than X, and X is never more than one mark ahead of O.

3. Off-by-One Errors in Diagonal Checks

When checking diagonals, it's easy to make indexing mistakes, especially for the anti-diagonal.

Incorrect approach:

# Wrong anti-diagonal check
if all(board[i][3 - i] == player for i in range(3)):  # Index out of bounds!
    return True

# Or using wrong formula
if all(board[i][2 - i - 1] == player for i in range(3)):  # Wrong indices!
    return True

Correct solution:

# Anti-diagonal: indices should be (0,2), (1,1), (2,0)
if all(board[i][2 - i] == player for i in range(3)):
    return True

The formula 2 - i correctly generates the column indices 2, 1, 0 as row index i goes from 0, 1, 2.