794. Valid Tic-Tac-Toe State

MediumArrayMatrix

Problem Description

In this problem, we are given the current state of a Tic-Tac-Toe board represented as an array of strings. Our goal is to determine whether this board configuration could have been reached in the course of a valid game. The board is of size 3 x 3, and the characters 'X', 'O', and ' ' represent the moves by the first player, the second player, and an empty space, respectively.

Tic-Tac-Toe is played according to these rules:

Two players take turns to make their move.
The first player uses 'X' and the second player uses 'O'.
Players can only place their marks in empty squares (' ').
The game ends either when a player has filled a row, column, or diagonal with their character, or when all the squares are filled, rendering the game over.
Once the game has ended, no further moves can be made.

We must verify if the given board could logically be the result of playing a game following these rules.

Intuition

To provide a valid solution, a few simple checks must be implemented based on the game's rules.

Count the occurrences of 'X' and 'O'. Since players alternate turns starting with 'X', there should either be an equal number of both or one more 'X' than 'O'.
Check for winners. Since the game stops as soon as a winning condition is met:
- If 'X' has won, there must be exactly one more 'X' than 'O' on the board—because 'X' plays first and would have just played to win the game.
- If 'O' has won, there must be an equal number of 'X' and 'O' on the board since 'O' would have just played to win the game.
Understand that both 'X' and 'O' cannot win in a single game instance—it would against game rules.

The code given first defines a function, win(x), which checks for winning conditions for the character x. It checks all rows, columns, and both diagonals to see if any of them are filled with the same character. The code then counts the number of 'X's and 'O's on the board. Lastly, it applies the previous two checks: it confirms the counts are appropriate given the rules, and it ensures that only one (or none) of the players could have possibly won the game. If any of these conditions fail, the board state is impossible, and the function returns False. Otherwise, it returns True.

By decomposing the problem into these logical steps, we can arrive at a clear solution approach that aligns with the rules of Tic-Tac-Toe.

Solution Approach

The solution is implemented in Python and uses simple iterative constructs to verify the validity of the given Tic-Tac-Toe board configuration.

Here are the key components of the solution approach:

Counting 'X' and 'O' Characters:
- The solution starts by counting the number of 'X' and 'O' characters present on the board utilizing list comprehensions.
- It's done by looping through each cell in the board using two nested loops (one for rows and one for columns) and incrementing the count appropriately for each character.
Winning Check Function (win(x)):
- The function win(x) takes a character x as an input and checks if that character has a win condition on the board.
- It checks for a win in each row, in each column, and across both diagonals. The all function is used to simplify the check within each row, column, or diagonal.
- If any win condition is met, it returns True. Otherwise, it returns False.
Game Rules Logic:
- After counting 'X's and 'O's, the code checks if their counts are valid. According to the rules, there cannot be more 'O's than 'X's, and 'X's can have at most one more than 'O' because they start the game. If these conditions are not met, the function returns False.
- Then, it checks if 'X' has won. If 'X' has won, there must be one more 'X' than 'O', as 'X' would have just played the winning move. If there is no such count difference, the function returns False.
- Similarly, it checks if 'O' has won. If 'O' has won, the counts of 'X' and 'O' must be equal, as 'O' would have just played the winning move. If x does not equal o in count, then it returns False.
Final Validation:
- Lastly, the code ensures that both 'X' and 'O' have not won simultaneously. If either 'X' or 'O' is winning, their respective count checks must also pass, as previously described.

An understanding of how a Tic-Tac-Toe game progresses and ends is integral to the solution. The implementation leverages basic control structures and the inherent properties of the game rules to reach a conclusion. There's no use of advanced data structures since the problem can be solved with simple list iteration and condition checking.

By combining these logical steps, the code effectively validates if the final board state can be the result of a valid game of Tic-Tac-Toe.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a Tic-Tac-Toe board with the following configuration:

['X', 'X', 'O'],
['O', 'X', ' '],
[' ', ' ', 'O']

Using the solution approach, we'll walk through the validation process:

Counting 'X' and 'O' Characters:
- There are 3 'X' characters and 3 'O' characters on the board.
Winning Check Function (win(x)):
- We check if 'X' has a win condition:
  - No row or column is entirely filled with 'X'.
  - Diagonals do not have three 'X' either.
  - So, win('X') would return False.
- Next, we check if 'O' has a win condition:
  - No row or column is entirely filled with 'O'.
  - However, one diagonal (from the bottom right to the top left) is filled with 'O'.
  - So, win('O') would return True.
Game Rules Logic:
- Since 'O' has a win condition, and the count of 'X' and 'O' is equal, this matches the rule that 'O' must have won on the last move.
Final Validation:
- Since only 'O' has a win condition and the counts of 'X' and 'O' follow the rule associated with 'O' winning, the game board is a possible result of a valid Tic-Tac-Toe game.

This illustrates how the code would verify the validity of the given board configuration by applying simple checks that are tied to the game rules. The analysis confirms that this particular board could indeed represent a game of Tic-Tac-Toe that has been played correctly according to the standard rules.

Solution Implementation

1class Solution:
2    def validTicTacToe(self, board: List[str]) -> bool:
3        # Function to check if player with mark 'X' or 'O' has won
4        def has_winner(mark):
5            # Check for horizontal and vertical wins
6            for i in range(3):
7                if all(board[i][j] == mark for j in range(3)):
8                    return True
9                if all(board[j][i] == mark for j in range(3)):
10                    return True
11          
12            # Check for the two diagonal wins
13            if all(board[i][i] == mark for i in range(3)):
14                return True
15            return all(board[i][2 - i] == mark for i in range(3))
16
17        # Count the number of 'X's and 'O's on the board
18        count_x = sum(row.count('X') for row in board)
19        count_o = sum(row.count('O') for row in board)
20
21        # Check for the correct number of 'X's and 'O's
22        if count_x != count_o and count_x - 1 != count_o:
23            return False
24
25        # If 'X' has won, 'X' must be one more than 'O'
26        if has_winner('X') and count_x - 1 != count_o:
27            return False
28
29        # If 'O' has won, the count of 'X' and 'O' must be the same
30        if has_winner('O') and count_x != count_o:
31            return False
32
33        # The board is valid if it does not violate any of the above rules
34        return True
35

1class Solution {
2    private String[] board;
3
4    // Checks if the given Tic-Tac-Toe board state is valid
5    public boolean validTicTacToe(String[] board) {
6        this.board = board;
7        int countX = count('X'), countO = count('O');
8
9        // 'X' goes first so there must be either the same amount of 'X' and 'O'
10        // or one more 'X' than 'O'
11        if (countX != countO && countX - 1 != countO) {
12            return false;
13        }
14
15        // If 'X' has won, there must be one more 'X' than 'O'
16        if (hasWon('X') && countX - 1 != countO) {
17            return false;
18        }
19
20        // If 'O' has won, there must be the same number of 'X' and 'O'
21        return !(hasWon('O') && countX != countO);
22    }
23
24    // Checks if the given player has won
25    private boolean hasWon(char player) {
26        // Check all rows and columns
27        for (int i = 0; i < 3; ++i) {
28            if (board[i].charAt(0) == player && board[i].charAt(1) == player && board[i].charAt(2) == player) {
29                return true;
30            }
31            if (board[0].charAt(i) == player && board[1].charAt(i) == player && board[2].charAt(i) == player) {
32                return true;
33            }
34        }
35        // Check both diagonals
36        if (board[0].charAt(0) == player && board[1].charAt(1) == player && board[2].charAt(2) == player) {
37            return true;
38        }
39        return board[0].charAt(2) == player && board[1].charAt(1) == player && board[2].charAt(0) == player;
40    }
41
42    // Counts the number of times the given character appears on the board
43    private int count(char character) {
44        int count = 0;
45        for (String row : board) {
46            for (char cell : row.toCharArray()) {
47                if (cell == character) {
48                    ++count;
49                }
50            }
51        }
52        return count;
53    }
54}
55

1class Solution {
2public:
3    // Function to check the validity of a tic-tac-toe game board state
4    bool validTicTacToe(vector<string>& board) {
5
6        // Lambda to count occurrences of a provided character ('X' or 'O') on the board
7        auto countCharacter = [&](char character) {
8            int count = 0;
9            for (const auto& row : board) {      // Iterate through each row of the board
10                for (char cell : row) {          // Iterate through each cell in the row
11                    count += cell == character;  // Increment count if the cell matches the character
12                }
13            }
14            return count;
15        };
16
17        // Lambda to check if a given player has won the game
18        auto checkWin = [&](char player) {
19            // Check rows and columns for a win condition
20            for (int i = 0; i < 3; ++i) {
21                if (board[i][0] == player && board[i][1] == player && board[i][2] == player) return true;
22                if (board[0][i] == player && board[1][i] == player && board[2][i] == player) return true;
23            }
24            // Check both diagonals for a win condition
25            if (board[0][0] == player && board[1][1] == player && board[2][2] == player) return true;
26            return board[0][2] == player && board[1][1] == player && board[2][0] == player;
27        };
28
29        // Count the number of 'X' and 'O' on the board
30        int countX = countCharacter('X');
31        int countO = countCharacter('O');
32
33        // Check the game's rules:
34        // Rule 1: The number of 'X's must either be equal to or one more than the number of 'O's
35        if (countX != countO && countX - 1 != countO) return false;
36
37        // Rule 2: If 'X' has won, there must be one more 'X' than 'O'
38        if (checkWin('X') && countX - 1 != countO) return false;
39
40        // Rule 3: If 'O' has won, the number of 'X's and 'O's must be equal
41        if (checkWin('O') && countX != countO) return false;
42
43        // If all rules are satisfied, the board state is valid
44        return true;
45    }
46};
47

1/**
2 * Checks if a given tic-tac-toe board state is valid.
3 * @param {string[]} board - An array of strings representing the tic-tac-toe board.
4 * @return {boolean} - Returns true if the board state is valid, false otherwise.
5 */
6const validTicTacToe = (board: string[]): boolean => {
7    // Helper function to count occurrences of 'X' or 'O' on the board.
8    const countOccurrences = (char: string): number => {
9        return board.reduce((accumulator, currentRow) => {
10            return accumulator + [...currentRow].filter(c => c === char).length;
11        }, 0);
12    };
13
14    // Helper function to check if a player has won the game.
15    const hasWon = (char: string): boolean => {
16        // Check rows and columns for win
17        for (let i = 0; i < 3; ++i) {
18            if (board[i][0] === char && board[i][1] === char && board[i][2] === char) {
19                return true;
20            }
21            if (board[0][i] === char && board[1][i] === char && board[2][i] === char) {
22                return true;
23            }
24        }
25        // Check diagonals for win
26        if (board[0][0] === char && board[1][1] === char && board[2][2] === char) {
27            return true;
28        }
29        return board[0][2] === char && board[1][1] === char && board[2][0] === char;
30    };
31
32    // Count occurrences of 'X' and 'O'.
33    const xCount = countOccurrences('X');
34    const oCount = countOccurrences('O');
35  
36    // Ensure 'X' goes first and there's at most one more 'X' than 'O'
37    if (xCount !== oCount && xCount - 1 !== oCount) {
38        return false;
39    }
40
41    // Check for a win by 'X'. If 'X' has won, there must be one more 'X' than 'O'.
42    if (hasWon('X') && xCount - 1 !== oCount) {
43        return false;
44    }
45
46    // Check for a win by 'O'. If 'O' has won, there must be an equal number of 'X' and 'O'.
47    if (hasWon('O') && xCount !== oCount) {
48        return false;
49    }
50
51    // If none of the invalid conditions were met, the board is valid.
52    return true;
53};
54

Time and Space Complexity

Time Complexity

The time complexity of the validTicTacToe function is O(1) because the size of the board is fixed at 3x3, and the algorithm iterates over the 9 cells of the board a constant number of times to count occurrences of 'X' and 'O', and to check for wins.

To calculate x and o, we have two double loops that go through the 3x3 board, which would normally result in a time complexity of O(n^2). However, since the board size is constant and does not grow with input, it results in a fixed number of operations that do not depend on any input size variable, so it is O(1).

The win function is called at most two times (once for 'X' and once for 'O'). Within each call, it goes through each row, each column, and both diagonals to check for a win condition, which again, since the board is a fixed 3x3 size, results in a constant number of operations that are O(1).

Space Complexity

The space complexity of the validTicTacToe function is also O(1). No additional space is used that grows with the input size. The function only uses a fixed number of variables (x, o, and the board itself) and the space taken by the recursive stack during the calls to win doesn't depend on the input size since the depth of recursion is not affected by the input but by the fixed size of the 3x3 board.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Quick sort does not use divide and conquer

I don’t know