Watch 7 video solutions for Valid Tic-Tac-Toe State, a medium level problem involving Array, Matrix. This walkthrough by Coding Courses has 1,762 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a Tic-Tac-Toe board as a string array board, return true if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The board is a 3 x 3 array that consists of characters ' ', 'X', and 'O'. The ' ' character represents an empty square.
Here are the rules of Tic-Tac-Toe:
' '.'X' characters, while the second player always places 'O' characters.'X' and 'O' characters are always placed into empty squares, never filled ones.
Example 1:
Input: board = ["O "," "," "] Output: false Explanation: The first player always plays "X".
Example 2:
Input: board = ["XOX"," X "," "] Output: false Explanation: Players take turns making moves.
Example 3:
Input: board = ["XOX","O O","XOX"] Output: true
Constraints:
board.length == 3board[i].length == 3board[i][j] is either 'X', 'O', or ' '.Problem Overview: You receive a 3x3 Tic-Tac-Toe board represented as strings. The board may contain 'X', 'O', or empty cells. The task is to verify whether this board state could occur during a real game where players alternate turns and follow standard Tic-Tac-Toe rules.
The tricky part is not checking wins but validating whether the sequence of moves that produced the board is legal. Since players alternate turns and 'X' always starts first, the counts of moves and the presence of winning lines must follow strict rules.
Approach 1: Count and Validate Turns (O(1) time, O(1) space)
Iterate through the 3x3 board and count how many times 'X' and 'O' appear. In a valid game, X_count must either equal O_count or exceed it by exactly one because 'X' always plays first. After counting, scan the board for winning combinations across rows, columns, and diagonals.
If 'X' wins, there must be exactly one more 'X' move than 'O'. If 'O' wins, both players must have the same number of moves. Any board where both players win simultaneously is invalid. This approach works by directly enforcing the logical constraints of the game rather than simulating moves. The board size is fixed, so scanning rows, columns, and diagonals takes constant time.
This approach primarily operates on the board grid itself, making it a straightforward use of array traversal and matrix pattern checking.
Approach 2: Mathematical Logical Check (O(1) time, O(1) space)
Instead of treating validation as multiple independent checks, you can encode the rules as mathematical conditions. First compute the counts of 'X' and 'O'. Then compute two boolean flags: whether 'X' has a winning line and whether 'O' has a winning line. Each flag is determined by checking the 8 possible win patterns.
Once you have these values, apply logical constraints: the difference between move counts must be valid, both players cannot win simultaneously, and the winning player must match the move order rules. For example, if xWin is true but X_count == O_count, the state is impossible because 'X' must have just played.
This approach condenses the entire validation into a small set of boolean conditions. It is often preferred when you want a clean and interview-friendly implementation with minimal branching.
Recommended for interviews: The count-and-validate approach is what most interviewers expect. It shows that you understand the game constraints and can systematically check rows, columns, and diagonals. The mathematical logical check is slightly cleaner once you recognize the constraints, but both run in constant time and space due to the fixed 3x3 board.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count and Validate Turns | O(1) | O(1) | Best general approach. Easy to reason about and clearly follows Tic-Tac-Toe rules. |
| Mathematical Logical Check | O(1) | O(1) | When you want a concise implementation using logical constraints instead of step-by-step validation. |