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:
- Turn Order:
Xalways goes first, followed by alternating turns (X, thenO). - 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
Xstarts, there can be at most one more"X"than"O". Specifically:count("X") == count("O")(if it’s O’s turn or game over) ORcount("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 (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:
- Count Constraint: The number of
Xs must be equal to or exactly one greater than the number ofOs. Ifcount("O") > count("X"), it’s impossible because O cannot move before X, and they alternate strictly. - Win Consistency:
- If
Xhas won,Xmust have just moved (socount("X") == count("O") + 1). Additionally,Ocannot have a winning line because the game would have ended before O could complete their win. - If
Ohas won, it implies X did not move after that turn, so counts must be equal (count("X") == count("O")). Also,Xcannot have a winning line for the same reason as above.
- If
Approach
- Count Characters: Iterate through the board to calculate total occurrences of
"X"and"O". Let these be and . Validate that . If not, returnFalseimmediately. - Check Win States: Implement a helper function or logic to check if there is any winning line for
"X"() and/or"O"(). A win exists if three identical characters occupy a row, column, or diagonal. - Apply Logic Rules:
- If both and are true: Return
False(game would have ended earlier). - If only is true: Check if . If not, return
False. Otherwise valid. - If only is true: Check if . If not, return
False. Otherwise valid. - If neither won: The state must be a draw or in-progress. Since counts are already validated (), this case returns
True(provided the board isn’t full with mismatched turns which is covered by count check).
- If both and are true: Return
Complexity Analysis
- Time Complexity: . Although we iterate over cells, a Tic-Tac-Toe board has fixed dimensions ( cells). Therefore, operations are constant time relative to input size. If generalized for an grid, it would be where .
- Space Complexity: . 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 , it implies O made a move after X completed their winning line (impossible). The code enforces
return x_count == o_count + 1in thex_winsbranch, catching this. - O Wins with Unequal Counts: If O wins but , 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 () correctly as valid.