Practice/Microsoft/Leetcode 794. Valid Tic-Tac-Toe State

Leetcode 794. Valid Tic-Tac-Toe State

CodingMust

Problem

You are given a 3x3 game board represented as an array of three strings, where each string represents a row. Each position on the board contains either 'X', 'O', or a space ' ' (representing an empty cell).

The game follows standard rules where X always makes the first move, and players alternate turns. The game ends immediately when one player gets three of their marks in a row (horizontally, vertically, or diagonally), or when all cells are filled.

Your task is to determine whether the given board state could have been reached through valid gameplay. You need to verify that:

• The turn order rules are respected (X goes first, proper alternation)
• If there's a winner, the game would have ended at that point
• No impossible configurations exist

Return true if the board state is valid, false otherwise.

Requirements

1. Verify that piece counts respect turn order (X goes first)
2. Check if either player has won
3. If there's a winner, ensure no additional moves were made after the winning condition
4. Handle all possible winning configurations (rows, columns, diagonals)
5. Ensure both players cannot be in a winning state simultaneously

Constraints

• board.length == 3
• board[i].length == 3
• board[i][j] is either 'X', 'O', or ' ' (space character)
• Time complexity should be O(1) since the board size is fixed
• Space complexity should be O(1)

Examples

Example 1:

Input: board = ["XOX", "O O", "X "] Output: true Explanation: X has 3 pieces, O has 2 pieces. No winner yet. This represents a valid game in progress where O will move next.

Example 2:

Input: board = ["XXX", "OOX", "OO "] Output: false Explanation: X won with three in the top row. However, O has 4 pieces and X has 4 pieces, meaning O placed a piece after X already won. This violates the rule that the game ends immediately upon winning.

Example 3:

Input: board = ["XOX", "OXO", "OXX"] Output: true Explanation: X has won with a diagonal (top-left to bottom-right). X has 5 pieces and O has 4 pieces, which is correct since X made the winning move.

Example 4:

Input: board = ["XOX", "OOX", "XOX"] Output: false Explanation: Both X and O have three in a column. This is impossible since the game would have ended when the first player completed their line.