Skip to main content
Talentd

Valid Tic-Tac-Toe State - Solution & Explanation

MediumArrayMatrix19 min readAsked at: Amazon, Microsoft, Tiktok
Practice this problem

Problem Statement

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:

  • Players take turns placing characters into empty squares ' '.
  • The first player always places 'X' characters, while the second player always places 'O' characters.
  • 'X' and 'O' characters are always placed into empty squares, never filled ones.
  • The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty.
  • No more moves can be played if the game is over.

 

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 == 3
  • board[i].length == 3
  • board[i][j] is either 'X', 'O', or ' '.

Approach Overview

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 1: Approach 1: Count and Validate Turns

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) - We process a fixed 3x3 board.
Space Complexity: O(1) - No additional space is required.

Try this approach in the editor →

Approach 2: Approach 2: Mathematical Logical Check

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) - Counting and evaluations over fixed iterations.
Space Complexity: O(1) - Limited variables allocated and reused across calls.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Count and Validate Turns

Time Complexity: O(1) - We process a fixed 3x3 board.
Space Complexity: O(1) - No additional space is required.

Approach 2: Mathematical Logical Check

Time Complexity: O(1) - Counting and evaluations over fixed iterations.
Space Complexity: O(1) - Limited variables allocated and reused across calls.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Count and Validate TurnsO(1)O(1)Best general approach. Easy to reason about and clearly follows Tic-Tac-Toe rules.
Mathematical Logical CheckO(1)O(1)When you want a concise implementation using logical constraints instead of step-by-step validation.

Video Solution

Valid Tic-Tac-Toe State | Top Google Coding Interview Question • Coding Courses • 1,801 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Valid Tic-Tac-Toe State easy or hard?
Valid Tic-Tac-Toe State is typically classified as a Medium problem. The board traversal is simple, but the challenge lies in correctly enforcing all game constraints and handling edge cases such as simultaneous wins or invalid move counts.
Valid Tic-Tac-Toe State Python/Java solution
Most implementations follow the same pattern: count 'X' and 'O', write a helper function to check whether a player has a winning line, then validate the counts against the winner conditions. The logic translates directly across Python, Java, C++, JavaScript, and C#.
How to solve Valid Tic-Tac-Toe State in O(1)?
Scan the 3x3 board once to count 'X' and 'O'. Then check all rows, columns, and diagonals to detect if either player has a winning line. Apply logical constraints: X must have either the same number of moves as O or exactly one more, both players cannot win simultaneously, and the winner must match the move count rule.
What is the best approach for Valid Tic-Tac-Toe State?
The count-and-validate approach is the most reliable solution. Count how many 'X' and 'O' moves exist, then verify winning lines across rows, columns, and diagonals. Apply the game rules: 'X' starts first, move counts must differ by at most one, and the winning player must match the move order. This method runs in O(1) time because the board size is fixed.
Is Valid Tic-Tac-Toe State asked at Google/Amazon/Meta?
Variants of board validation and game-state checking problems appear in interviews at companies like Google, Amazon, and Meta. The problem tests logical reasoning, matrix traversal, and edge-case handling rather than heavy algorithmic complexity.
What data structure is used in Valid Tic-Tac-Toe State?
The primary data structure is a 2D board represented as a matrix or array of strings. The solution iterates through the matrix to count symbols and evaluate row, column, and diagonal win patterns.
What is the time complexity of Valid Tic-Tac-Toe State?
The time complexity is O(1). The board is always a fixed 3x3 grid, so counting symbols and checking the 8 possible winning lines takes constant time regardless of input. Space complexity is also O(1) since only a few counters and boolean flags are used.

Ready to solve this problem?

Practice Valid Tic-Tac-Toe State with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Tic-Tac-Toe