794. Valid Tic-Tac-Toe State
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.
- If
-
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.
Which data structure is used to implement priority queue?
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.
- The solution starts by counting the number of
-
Winning Check Function (
win(x)):- The function
win(x)takes a characterxas 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
allfunction is used to simplify the check within each row, column, or diagonal. - If any win condition is met, it returns
True. Otherwise, it returnsFalse.
- The function
-
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 returnsFalse. - 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 returnsFalse. - 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. Ifxdoes not equaloin count, then it returnsFalse.
- After counting
-
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.
- Lastly, the code ensures that both
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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Example Walkthrough
Let's consider a Tic-Tac-Toe board with the following configuration:
1['X', 'X', 'O'], 2['O', 'X', ' '], 3[' ', ' ', '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.
- There are 3
-
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 returnFalse.
- No row or column is entirely filled with
- 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 returnTrue.
- No row or column is entirely filled with
- We check if
-
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.
- Since
-
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.
- Since only
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
351class 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}
551class 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};
471/**
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};
54How does quick sort divide the problem into subproblems?
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.
Which of the following uses divide and conquer strategy?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.