Valid Tic-Tac-Toe State: Invariant Checking

LeetCode 794: Valid Tic-Tac-Toe State gives you a tic-tac-toe board as an array of 3 strings, where each character is 'X', 'O', or ' '. Your job is to determine whether the board could have been reached through legal play. X always goes first, players alternate turns, and the game ends as soon as someone wins or the board is full.

The board is just 9 cells. There is no search, no recursion, no dynamic programming. The entire problem comes down to checking a handful of invariants. If any invariant is violated, the board is impossible. If all hold, it is valid.

Why this problem matters

At first glance this feels like a toy problem. The board is tiny and the rules are simple. But the challenge is not about scale. It is about completeness. You need to identify every constraint that a legal game imposes on the board and check all of them without missing any.

This is the same skill you use when validating user input, enforcing business rules, or writing assertions in a test suite. The question is always: what invariants must hold, and have I covered them all?

Missing even one check (like forgetting that the game stops when someone wins) leads to accepting impossible boards. The problem trains you to think exhaustively about constraints before writing code, which is exactly what interviewers want to see.

The approach

There are five rules that every valid tic-tac-toe board must satisfy:

1. Turn count: Count all X's and O's on the board. Since X always goes first, the number of X's must equal the number of O's (O just played) or the number of O's plus one (X just played). Any other count is impossible.

2. Check X wins: Scan all 8 possible winning lines (3 rows, 3 columns, 2 diagonals). If all three cells in any line are 'X', then X has won.

3. Check O wins: Same scan, looking for three 'O's in a line.

4. Win timing: If X wins, the game must have ended on X's turn. That means X count equals O count plus one. If O wins, the game ended on O's turn, so X count equals O count.

5. No double win: Both players cannot have three in a row at the same time. That would require play to continue after the first win, which is illegal.

If all five checks pass, the board is valid. Otherwise it is not.

Clean solution

def validTicTacToe(board: list[str]) -> bool:
    x_count = sum(row.count('X') for row in board)
    o_count = sum(row.count('O') for row in board)

    if x_count != o_count and x_count != o_count + 1:
        return False

    def wins(player: str) -> bool:
        for i in range(3):
            if all(board[i][j] == player for j in range(3)):
                return True
            if all(board[j][i] == player for j in range(3)):
                return True
        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 = wins('X')
    o_wins = wins('O')

    if x_wins and o_wins:
        return False
    if x_wins and x_count != o_count + 1:
        return False
    if o_wins and x_count != o_count:
        return False

    return True

Step-by-step walkthrough

The algorithm is a checklist. You compute the counts, check for winners, then verify that the counts and winners are consistent with each other. There is no branching logic to reason about, no data structures to maintain. Each check either passes or it does not.

The reason this works is that tic-tac-toe has very few degrees of freedom. The board is 3x3, X always goes first, and the game ends immediately on a win. These constraints are tight enough that a small set of invariants captures every possible violation.

Complexity analysis

The board is always 3x3, which means exactly 9 cells and exactly 8 possible winning lines. Counting X's and O's takes 9 character comparisons. Checking wins scans at most 8 lines of 3 cells each, which is 24 comparisons. Everything is bounded by a constant, so both time and space are O(1).

The building blocks

1. Constraint enumeration

The hardest part of this problem is not writing the code. It is listing every constraint. Once you have the full list (turn count, X win timing, O win timing, no double win), the implementation is mechanical. This "enumerate then check" pattern shows up in any validation problem: valid Sudoku, valid parentheses, valid BST. The skill is being systematic enough to not miss a case.

if x_count != o_count and x_count != o_count + 1:
    return False
if x_wins and o_wins:
    return False
if x_wins and x_count != o_count + 1:
    return False
if o_wins and x_count != o_count:
    return False

2. Line scanning on a grid

Checking all rows, columns, and diagonals of a 3x3 grid is a reusable pattern. You check 3 rows, 3 columns, and 2 diagonals. The diagonal indices follow (i, i) and (i, 2 - i) for i in 0..2. This same scanning logic appears in N-Queens, Connect Four, and any grid game that cares about aligned cells.

Edge cases to watch for

• Empty board: All spaces. X count and O count are both 0. No winner. Valid.
• Full board with no winner: All 9 cells filled, no three in a row. X count is 5, O count is 4. Valid (a draw).
• X wins on the last move: X places the 5th X to complete a line. X count is 5, O count is 4. X wins and x_count == o_count + 1. Valid.
• O wins on the last move: O places the 4th O to complete a line. X count is 4, O count is 4. O wins and x_count == o_count. Valid.
• Both players have three in a row: Impossible in a real game because play stops after the first win. Return False.
• X wins but O count equals X count: This means O played after X already won. Invalid.
• O wins but X count equals O count plus one: This means X played after O already won. Invalid.
• Too many O's: O count greater than X count is always invalid because X goes first.

From understanding to recall

You have walked through the five invariants and understand why each one is necessary. The logic is clean: count, scan, cross-check. But under interview pressure, it is easy to forget one of the win-timing checks or mix up which count condition goes with which player.

Spaced repetition fixes this. You practice writing the count check, the win scanner, and the three cross-validation rules from scratch. Do it today, again in two days, again in five. After a few reps, you see "valid game state" and the invariant checklist flows out automatically.

Invariant checking and line scanning are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Valid Sudoku - Another grid validation problem checking row/column/box constraints
• Game of Life - Grid state analysis with neighbor counting
• Set Matrix Zeroes - Matrix analysis and state tracking