#794

Medium

LeetCode Problem Workspace

Valid Tic-Tac-Toe State

Verify if a given Tic-Tac-Toe board can represent a valid game state during a valid sequence of moves.

Problem Statement

You are given a Tic-Tac-Toe board represented by a 3x3 string array. Each element is either 'X', 'O', or a space character, representing empty squares. You must determine if the board can represent a valid game state, considering the rules of Tic-Tac-Toe.

The game alternates turns between two players. Player 'X' always starts first. A valid board configuration must adhere to the alternating move pattern and must not allow multiple winners or an invalid number of moves. The task is to check if the board state could have been reached legally during a game.

Examples

Example 1

Input: board = ["O "," "," "]

Output: false

The first player always plays "X".

Example 2

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

Output: false

Players take turns making moves.

Example 3

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

Output: true

Example details omitted.

Constraints

board.length == 3
board[i].length == 3
board[i][j] is either 'X', 'O', or ' '.

Solution Approach

Count 'X' and 'O' Moves

The first step is to count the number of 'X' and 'O' moves. Since player 'X' starts first, the number of 'X' should always be equal to or one greater than the number of 'O' moves. If the counts do not match these rules, the board configuration is invalid.

Check for Winner

Next, check for a winner by evaluating rows, columns, and diagonals for three consecutive 'X' or 'O' characters. If both 'X' and 'O' appear as winners, the board is invalid. Additionally, if 'X' wins, the count of 'X' must be exactly one more than 'O'.

Validate Player Turn Sequence

Finally, ensure that the game alternates moves correctly. If player 'O' is the winner, there must be an equal number of 'X' and 'O'. If player 'X' is the winner, there must be one more 'X' than 'O'. If either condition is violated, the board state is invalid.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used to check rows, columns, and diagonals, but it is typically O(1) due to the fixed size of the board. Space complexity is also O(1) as only a few variables are needed for counting and checking conditions.

What Interviewers Usually Probe

Can the candidate correctly identify when the board counts for 'X' and 'O' are invalid?
Is the candidate able to logically check for a valid winner without errors?
Does the candidate understand the alternating move sequence and its effect on validity?

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for the fact that 'X' always starts first.
Overlooking the case where both players are declared winners simultaneously.
Incorrectly counting moves, leading to an invalid board state.

Follow-up variants

Consider larger boards or different-sized Tic-Tac-Toe grids for extension of the problem.
Validate different sets of rules for non-standard Tic-Tac-Toe games.
Check for invalid inputs or malformed boards as an edge case.

FAQ

What is the main algorithmic pattern in the 'Valid Tic-Tac-Toe State' problem?

The main pattern involves validating the game board by counting moves, checking for winners, and ensuring the sequence of turns is correct.

What are the most common mistakes when solving the 'Valid Tic-Tac-Toe State' problem?

The most common mistakes include counting 'X' and 'O' moves incorrectly or failing to correctly handle the game’s alternating turns.

Can I solve the 'Valid Tic-Tac-Toe State' problem with a brute force approach?

While a brute force approach is possible, it's generally inefficient. The problem can be solved efficiently by directly checking row, column, and diagonal patterns.

How does GhostInterview help me with 'Valid Tic-Tac-Toe State'?

GhostInterview guides you through step-by-step validation, helping you identify errors in the board state and ensuring you follow the correct game rules.

Are there any variations of the 'Valid Tic-Tac-Toe State' problem?

Yes, variations can include larger grids or different rules, such as a non-square board or a 3D Tic-Tac-Toe version.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        def win(x):
            for i in range(3):
                if all(board[i][j] == x for j in range(3)):
                    return True
                if all(board[j][i] == x for j in range(3)):
                    return True
            if all(board[i][i] == x for i in range(3)):
                return True
            return all(board[i][2 - i] == x for i in range(3))

        x = sum(board[i][j] == 'X' for i in range(3) for j in range(3))
        o = sum(board[i][j] == 'O' for i in range(3) for j in range(3))
        if x != o and x - 1 != o:
            return False
        if win('X') and x - 1 != o:
            return False
        return not (win('O') and x != o)

Continue Practicing

#803 bricks falling when hit #782 transform to chessboard #807 max increase to keep city skyline