LeetCode 794 - Valid Tic-Tac-Toe State

LeetCode Problem 794

Difficulty: 🟡 Medium
Topics: Array, Matrix

Solution

Problem Understanding

This problem asks us to determine whether a given Tic-Tac-Toe board configuration could occur during a real game that follows all official rules.

The input is a 3 x 3 board represented as an array of three strings. Each character in the strings can be:

• 'X', representing a move made by player X
• 'O', representing a move made by player O
• ' ', representing an empty square

The game rules matter because not every arrangement of X and O pieces is reachable during legal gameplay. We must verify whether the board could have been produced by alternating turns starting from an empty board.

Several important rules constrain valid states:

1. Player X always moves first.
2. Players alternate turns.
3. A move can only be placed into an empty cell.
4. The game immediately ends when either player gets three in a row.
5. No moves are allowed after the game ends.

The output should be true if the board could exist during some valid game, otherwise false.

The constraints are very small. The board always contains exactly 9 cells, so efficiency is not a concern. Even a brute-force solution is feasible. However, the challenge is reasoning correctly about all game rules and edge cases.

Several edge cases are especially important:

• Boards where O has more moves than X, which is impossible because X starts first.
• Boards where X has more than one extra move compared to O.
• Boards where both players have winning lines simultaneously.
• Boards where a player continues making moves after someone already won.
• Boards with multiple winning lines for one player, which can still be valid if created on the final move.

The problem guarantees that the board dimensions are always valid, so we only need to validate gameplay consistency.

Approaches

Brute Force Approach

The brute-force approach is to simulate every possible Tic-Tac-Toe game from an empty board and store all reachable states. Then, for the input board, we simply check whether it exists among the generated states.

Since Tic-Tac-Toe has a very small state space, this is actually computationally feasible. We can recursively generate all legal moves, stop whenever a player wins, and collect every reachable configuration.

This approach is correct because it explicitly models every valid game sequence. If a board appears in the generated set, it must be reachable legally.

However, this method is unnecessarily complicated for such a small logical validation problem. It requires recursion, state serialization, and maintaining a visited set. The implementation becomes larger and harder to reason about than necessary.

Optimal Logical Validation Approach

The key observation is that a valid Tic-Tac-Toe board must satisfy several mathematical and structural properties derived directly from the game rules.

Instead of simulating every game, we can validate the board using these conditions:

1. X must have either the same number of moves as O, or exactly one more.
2. If X wins, then X must have one extra move.
3. If O wins, then X and O must have the same number of moves.
4. Both players cannot win simultaneously.

These rules fully characterize all valid board states.

Once we count the number of X and O moves and determine whether either player has a winning line, validation becomes straightforward.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^9)	O(3^9)	Generates all reachable board states recursively
Optimal	O(1)	O(1)	Validates board using move counts and win conditions

Algorithm Walkthrough

1. Count the number of X and O moves on the board.

Since X always moves first and players alternate turns, the number of X moves must either equal the number of O moves or exceed it by exactly one.

Therefore:

• o_count > x_count is invalid
• x_count > o_count + 1 is invalid

2. Create a helper function to determine whether a player has won.

A player wins if they occupy:

• Any row
• Any column
• Either diagonal

The helper function checks all 8 possible winning lines. 3. Determine whether X has won.

If X has a winning line, then X must have made the final move. Since X always moves first, this means:

x_count == o_count + 1

If this condition is not true, the board is invalid. 4. Determine whether O has won.

If O has a winning line, then O must have made the final move. Therefore:

x_count == o_count

Otherwise, the board is invalid. 5. Check whether both players have winning lines simultaneously.

This can never happen in a legal game because the game stops immediately after the first win.

Therefore, if both players win, return false. 6. If all checks pass, return true.

Why it works

The algorithm works because Tic-Tac-Toe has strict structural constraints derived from alternating turns and immediate game termination after a win.

The move count rules ensure turn order consistency. The winning conditions ensure the final move belongs to the player who created the winning line. The simultaneous-win check guarantees that the game could not have continued after a victory.

Together, these conditions completely characterize every valid Tic-Tac-Toe state.

Python Solution

from typing import List

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        x_count = 0
        o_count = 0

        for row in board:
            for cell in row:
                if cell == 'X':
                    x_count += 1
                elif cell == 'O':
                    o_count += 1

        # X always goes first
        if o_count > x_count:
            return False

        # X can have at most one extra move
        if x_count > o_count + 1:
            return False

        def has_won(player: str) -> bool:
            # Check rows
            for row in range(3):
                if all(board[row][col] == player for col in range(3)):
                    return True

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

            # Check diagonals
            if all(board[i][i] == player for i in range(3)):
                return True

            if all(board[i][2 - i] == player for i in range(3)):
                return True

            return False

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

        # Both players cannot win
        if x_wins and o_wins:
            return False

        # If X wins, X must have one more move
        if x_wins and x_count != o_count + 1:
            return False

        # If O wins, counts must be equal
        if o_wins and x_count != o_count:
            return False

        return True

The implementation begins by counting all X and O moves. This allows us to verify whether turn ordering is possible.

Next, the has_won helper checks every winning line. Since Tic-Tac-Toe only has eight possible winning patterns, the function remains very small and efficient.

After computing x_wins and o_wins, the algorithm validates the board using logical rules derived from the game mechanics.

The implementation directly mirrors the reasoning from the algorithm walkthrough, which makes it easy to verify correctness.

Go Solution

func validTicTacToe(board []string) bool {
    xCount := 0
    oCount := 0

    for _, row := range board {
        for _, cell := range row {
            if cell == 'X' {
                xCount++
            } else if cell == 'O' {
                oCount++
            }
        }
    }

    // X always moves first
    if oCount > xCount {
        return false
    }

    // X can have at most one extra move
    if xCount > oCount+1 {
        return false
    }

    hasWon := func(player byte) bool {
        // Rows
        for row := 0; row < 3; row++ {
            if board[row][0] == player &&
                board[row][1] == player &&
                board[row][2] == player {
                return true
            }
        }

        // Columns
        for col := 0; col < 3; col++ {
            if board[0][col] == player &&
                board[1][col] == player &&
                board[2][col] == player {
                return true
            }
        }

        // Main diagonal
        if board[0][0] == player &&
            board[1][1] == player &&
            board[2][2] == player {
            return true
        }

        // Anti-diagonal
        if board[0][2] == player &&
            board[1][1] == player &&
            board[2][0] == player {
            return true
        }

        return false
    }

    xWins := hasWon('X')
    oWins := hasWon('O')

    // Both players cannot win
    if xWins && oWins {
        return false
    }

    // If X wins, X must have one extra move
    if xWins && xCount != oCount+1 {
        return false
    }

    // If O wins, move counts must match
    if oWins && xCount != oCount {
        return false
    }

    return true
}

The Go implementation follows the same logic as the Python version. One small difference is that strings in Go are indexed as bytes, so the helper function accepts a byte instead of a string character.

Because the board size is fixed, there are no concerns about integer overflow or memory usage.

Worked Examples

Example 1

board = ["O  ",
         "   ",
         "   "]

Step 1: Count moves

Cell Type	Count
X	0
O	1

Now check move validity:

o_count > x_count
1 > 0

This is impossible because X always moves first.

Return false.

Example 2

board = ["XOX",
         " X ",
         "   "]

Step 1: Count moves

Cell Type	Count
X	3
O	1

Check move counts:

x_count > o_count + 1
3 > 2

This means X played twice in a row.

Return false.

Example 3

board = ["XOX",
         "O O",
         "XOX"]

Step 1: Count moves

Cell Type	Count
X	4
O	4

Move counts are valid.

Step 2: Check wins

Player	Winning Line
X	No
O	No

Neither player wins.

Step 3: Final validation

• Counts are valid
• No simultaneous wins
• No invalid winner state

Return true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The board size is fixed at 3 x 3
Space	O(1)	Only a few counters and variables are used

Although the algorithm loops through rows, columns, and diagonals, the board size never changes. Every operation touches at most 9 cells, so the runtime is constant.

The helper function also checks a fixed number of winning patterns, which keeps memory usage constant as well.

Test Cases

solution = Solution()

assert solution.validTicTacToe(
    ["O  ", "   ", "   "]
) is False  # O cannot move first

assert solution.validTicTacToe(
    ["XOX", " X ", "   "]
) is False  # X moved too many times

assert solution.validTicTacToe(
    ["XOX", "O O", "XOX"]
) is True  # valid completed game

assert solution.validTicTacToe(
    ["XXX", "   ", "OOO"]
) is False  # both players cannot win

assert solution.validTicTacToe(
    ["XXX", "OOX", "OOX"]
) is True  # valid X victory

assert solution.validTicTacToe(
    ["XOX", "OXO", "XOX"]
) is True  # full valid draw board

assert solution.validTicTacToe(
    ["XXX", "XOO", "OO "]
) is False  # X has too many moves after winning

assert solution.validTicTacToe(
    ["OOO", "XX ", "XX "]
) is False  # O cannot win with fewer X moves

assert solution.validTicTacToe(
    ["   ", "   ", "   "]
) is True  # empty board is valid

assert solution.validTicTacToe(
    ["X  ", "   ", "   "]
) is True  # first move by X

assert solution.validTicTacToe(
    ["XXO", "OOX", "XOX"]
) is True  # balanced valid state

assert solution.validTicTacToe(
    ["XXX", "OO ", "   "]
) is True  # X wins on final move

Test	Why
["O "," "," "]	Verifies O cannot move first
["XOX"," X "," "]	Verifies alternating turn rules
["XOX","O O","XOX"]	Valid draw configuration
["XXX"," ","OOO"]	Detects simultaneous winners
["XXX","OOX","OOX"]	Valid X winning state
["XOX","OXO","XOX"]	Full board with no winner
["XXX","XOO","OO "]	Detects moves after game should end
["OOO","XX ","XX "]	O win with invalid move counts
[" "," "," "]	Empty board edge case
["X "," "," "]	Earliest valid move
["XXO","OOX","XOX"]	Mixed valid mid-game state
["XXX","OO "," "]	Valid immediate X victory

Edge Cases

Both Players Winning Simultaneously

A board where both X and O have winning lines is impossible in legal Tic-Tac-Toe. The game stops immediately after the first winning move, so the second player never gets another turn to create their own win.

For example:

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

A naive implementation that only checks whether someone won could incorrectly accept this board. The implementation explicitly rejects states where both x_wins and o_wins are true.

Invalid Move Counts

Since X always starts and players alternate turns, the move counts are tightly constrained.

Examples of invalid states include:

["OO ",
 "   ",
 "   "]

and

["XXX",
 "   ",
 "   "]

The first has too many O moves, while the second has too many X moves without enough O responses.

The implementation handles this using:

if o_count > x_count:
    return False

if x_count > o_count + 1:
    return False

Winning Player With Incorrect Turn Count

A subtle bug occurs when a player wins but the move counts indicate the other player moved afterward.

Example:

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

Even if only one player won, the move counts might contradict the timing of that victory.

If X wins, X must have played the final move, so X must have exactly one more move than O.

If O wins, both counts must match.

The implementation enforces these conditions directly after computing winning states.