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.
This approach involves counting the number of 'X' and 'O' on the board and validating a tic-tac-toe board based on the count and winning conditions.
1. Count the number of 'X' and 'O'.
2. Ensure that the number of 'O's is not greater than the number of 'X's and that the number of 'X's does not exceed the number of 'O's by more than one.
3. Check win states for 'X' and 'O'.
4. If both players have a winning line, the board is invalid.
The goal is to ensure the board could have been created by valid game play.
This solution checks for a valid Tic-Tac-Toe game state by counting the 'X's and 'O's and ensuring that their counts are within allowable ranges. It also checks for win conditions and ensures the board is a valid state based on who's supposed to win.
Time Complexity: O(1) - We process a fixed 3x3 board.
Space Complexity: O(1) - No additional space is required.
In this approach, we don't just account for the counts but also utilize a logical check to directly evaluate win conditions and ensure the configuration aligns with tic-tac-toe game rules.
1. Assess characters' count to validate play sequence.
2. Use mathematical logic to quickly determine if any win condition is met by checking all board positions.
3. Ensure there's no possibility of two winners in the current game state.
The aim is to provide a quick validity response based on the typical outcomes of a tic-tac-toe game.
This solution involves counting each player's moves and checking for a valid win state configuration using an optimally logical approach to aid the count checks.
Time Complexity: O(1) - Counting and evaluations over fixed iterations.
Space Complexity: O(1) - Limited variables allocated and reused across calls.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Count and Validate Turns | Time Complexity: O(1) - We process a fixed 3x3 board. |
| Approach 2: Mathematical Logical Check | Time Complexity: O(1) - Counting and evaluations over fixed iterations. |
| Default Approach | — |
| 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. |
Valid Tic-Tac-Toe State | Top Google Coding Interview Question • Coding Courses • 1,762 views views
Watch 6 more video solutions →Practice Valid Tic-Tac-Toe State with our built-in code editor and test cases.
Practice on FleetCode