How do you solve Valid Tic-Tac-Toe State on LeetCode?

Valid Tic-Tac-Toe State (LeetCode #794) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The count of 'X's must always be equal to or one more than the count of 'O's.

What is the brute force solution for Valid Tic-Tac-Toe State?

The brute force approach for Valid Tic-Tac-Toe State is Brute Force, with O(n²) time complexity and O(1) space complexity. We can simply count the occurrences of 'X' and 'O' on the board and check the game rules based on these counts. If the counts violate the rules of Tic-Tac-Toe, we can determine that the board state is invalid. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Valid Tic-Tac-Toe State?

Valid Tic-Tac-Toe State uses the following concepts: Array, Matrix. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Valid Tic-Tac-Toe State?

Always clarify the rules of the game before diving into the solution. Think about edge cases, such as an empty board or a board that is already full. Explain your thought process clearly as you write your code.

What are common mistakes when solving Valid Tic-Tac-Toe State?

Failing to check the counts of 'X' and 'O' correctly. Not considering the winning conditions properly, especially when both players seem to win.

#794

Valid Tic-Tac-Toe State

Medium

ArrayMatrixHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

We can optimize the checking process by directly evaluating the winning conditions while counting 'X' and 'O'. This reduces the need for multiple passes over the board.

⚙️

Algorithm

3 steps

1Step 1: Initialize counts for 'X' and 'O', and flags for winning conditions.
2Step 2: Iterate through the board to count 'X's and 'O's, and check winning conditions simultaneously.
3Step 3: Validate the counts and winning conditions to determine if the board state is valid.

solution.py23 lines

1def validTicTacToe(board):
2    x_count = o_count = 0
3    x_win = o_win = False
4    for i in range(3):
5        x_count += board[i].count('X')
6        o_count += board[i].count('O')
7        if board[i] == 'XXX' or board[0][i] == board[1][i] == board[2][i] == 'X':
8            x_win = True
9        if board[i] == 'OOO' or board[0][i] == board[1][i] == board[2][i] == 'O':
10            o_win = True
11    if board[0][0] == board[1][1] == board[2][2] == 'X' or board[0][2] == board[1][1] == board[2][0] == 'X':
12        x_win = True
13    if board[0][0] == board[1][1] == board[2][2] == 'O' or board[0][2] == board[1][1] == board[2][0] == 'O':
14        o_win = True
15    if o_count > x_count or x_count > o_count + 1:
16        return False
17    if x_win and o_win:
18        return False
19    if x_win and x_count != o_count + 1:
20        return False
21    if o_win and x_count != o_count:
22        return False
23    return True

ℹ

Complexity note: The time complexity is O(n) because we are making a single pass through the board to count and check wins, while the space complexity is O(1) as we are using a fixed amount of space.

1The count of 'X's must always be equal to or one more than the count of 'O's.
2A winning state for both players cannot occur simultaneously.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.