Problem

Given a Tic-Tac-Toe board as a string array board, return true if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array that consists of characters ' ', 'X', and 'O'. The ' ' character represents an empty square.

Here are the rules of Tic-Tac-Toe:

  • Players take turns placing characters into empty squares ' '.
  • The first player always places 'X' characters, while the second player always places 'O' characters.
  • 'X' and 'O' characters are always placed into empty squares, never filled ones.
  • The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty.
  • No more moves can be played if the game is over.

Examples

Example 1:

$$ \begin{array}{|c|c|c|} \hline \cellcolor{orange} O & & \ \hline & & \ \hline & & \ \hline \end{array} $$

Input: board = ["O  ","   ","   "]
Output: false
Explanation: The first player always plays "X".

Example 2:

$$ \begin{array}{|c|c|c|} \hline \cellcolor{lightblue} X & \cellcolor{orange} O & \cellcolor{lightblue} X \ \hline & \cellcolor{lightblue} X & \ \hline & & \ \hline \end{array} $$

Input: board = ["XOX"," X ","   "]
Output: false
Explanation: Players take turns making moves.

Example 3:

$$ \begin{array}{|c|c|c|} \hline \cellcolor{lightblue} X & \cellcolor{orange} O & \cellcolor{lightblue} X \ \hline \cellcolor{orange} O & & \cellcolor{orange} O \ \hline \cellcolor{lightblue} X & \cellcolor{orange} O & \cellcolor{lightblue} X \ \hline \end{array} $$

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

Solution

Method 1 - Simple Heuristics

Here are the key points:

  1. Player Turn Rules:
    • Since player ‘X’ always starts, the count of ‘X’ should be greater than or equal to the count of ‘O’. Therefore, if o_count > x_count, the board is invalid.
    • Players alternate turns, so the difference between the count of ‘X’ and ‘O’ should not exceed one. Thus, if x_count - o_count > 1, the board is invalid.
  2. Winning Conditions:
    • If player ‘O’ has a winning condition, ensure that player ‘X’ does not have a winning condition at the same time. This is because the game should stop as soon as a winning condition is met.
    • If player ‘O’ wins, then x_count should equal o_count since ‘O’ plays second and the counts must match up to this condition.
    • If player ‘X’ wins, then x_count should be exactly one more than o_count because ‘X’ starts first.
  3. Algorithm:
    • Check initial conditions for count validity.
    • Evaluate the board to see if either player has a winning configuration.
    • Validate that the counts and winning conditions align correctly based on the rules of the game.

Here is a more detailed explanation:

  1. Check Initial Count Validity:
    • If o_count > x_count, return False.
    • If x_count - o_count > 1, return False.
  2. Check Winning Conditions:
    • If player ‘O’ wins:
      • Ensure player ‘X’ does not also win. If both win, return False.
      • Ensure x_count == o_count. If not, return False.
    • If player ‘X’ wins:
      • Ensure x_count == o_count + 1. If not, return False.

Code

Java
class Solution {
    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                if (c == 'X') xCount++;
                if (c == 'O') oCount++;
            }
        }
        
        // Initial count validity
        if (oCount > xCount) return false;
        if (xCount > oCount + 1) return false;
        
        boolean xWins = isWinner(board, 'X');
        boolean oWins = isWinner(board, 'O');
        
        // Checking winning conditions
        if (oWins) {
            if (xWins) return false;  // Both can't win simultaneously
            if (xCount != oCount) return false;  // 'O' wins so counts must be equal
        }
        
        if (xWins) {
            if (xCount != oCount + 1) return false;  // 'X' wins so must have one more count than 'O'
        }
        
        return true;
    }
    
    private boolean isWinner(String[] board, char p) {
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(0) == p && board[i].charAt(1) == p && board[i].charAt(2) == p) return true;
            if (board[0].charAt(i) == p && board[1].charAt(i) == p && board[2].charAt(i) == p) return true;
        }
        if (board[0].charAt(0) == p && board[1].charAt(1) == p && board[2].charAt(2) == p) return true;
        if (board[0].charAt(2) == p && board[1].charAt(1) == p && board[2].charAt(0) == p) return true;
        
        return false;
    }
}
Python
class Solution:
    def validTicTacToe(self, board: List[str]) -> bool:
        x_count = sum(row.count('X') for row in board)
        o_count = sum(row.count('O') for row in board)

        # Initial count validity
        if o_count > x_count:
            return False
        if x_count > o_count + 1:
            return False

        x_wins = self.is_winner(board, 'X')
        o_wins = self.is_winner(board, 'O')
        
        # Checking winning conditions
        if o_wins:
            if x_wins:
                return False  # Both can't win simultaneously
            if x_count != o_count:
                return False  # 'O' wins so counts must be equal
        
        if x_wins:
            if x_count != o_count + 1:
                return False  # 'X' wins so must have one more count than 'O'
        
        return True

    def is_winner(self, board: List[str], p: str) -> bool:
        for i in range(3):
            if board[i][0] == p and board[i][1] == p and board[i][2] == p:
                return True
            if board[0][i] == p and board[1][i] == p and board[2][i] == p:
                return True
        if board[0][0] == p and board[1][1] == p and board[2][2] == p:
            return True
        if board[0][2] == p and board[1][1] == p and board[2][0] == p:
            return True
        
        return False
`

Complexity

  • ⏰ Time complexity: O(1), because the board size is fixed at 3 x 3. Checking each cell and verifying win conditions is constant.
  • 🧺 Space complexity: O(1), as no additional space proportional to input size is required beyond a few counters and boolean flags.