794. Valid Tic-Tac-Toe State - Leetcode Solution

Code Implementation

class Solution:
    def validTicTacToe(self, board):
        def win(player):
            # Check rows, columns, and diagonals
            for i in range(3):
                if all(board[i][j] == player for j in range(3)):
                    return True
                if all(board[j][i] == player for j in range(3)):
                    return True
            if all(board[i][i] == player for i in range(3)):
                return True
            if all(board[i][2-i] == player for i in range(3)):
                return True
            return False

        x_count = sum(row.count('X') for row in board)
        o_count = sum(row.count('O') for row in board)

        if o_count > x_count or x_count - o_count > 1:
            return False

        x_win = win('X')
        o_win = win('O')

        if x_win and o_win:
            return False
        if x_win and x_count != o_count + 1:
            return False
        if o_win and x_count != o_count:
            return False
        return True

class Solution {
public:
    bool win(vector<string>& board, char player) {
        for (int i = 0; i < 3; ++i) {
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player)
                return true;
            if (board[0][i] == player && board[1][i] == player && board[2][i] == player)
                return true;
        }
        if (board[0][0] == player && board[1][1] == player && board[2][2] == player)
            return true;
        if (board[0][2] == player && board[1][1] == player && board[2][0] == player)
            return true;
        return false;
    }

    bool validTicTacToe(vector<string>& board) {
        int x_count = 0, o_count = 0;
        for (auto& row : board) {
            for (char c : row) {
                if (c == 'X') x_count++;
                else if (c == 'O') o_count++;
            }
        }
        if (o_count > x_count || x_count - o_count > 1)
            return false;
        bool x_win = win(board, 'X');
        bool o_win = win(board, 'O');
        if (x_win && o_win) return false;
        if (x_win && x_count != o_count + 1) return false;
        if (o_win && x_count != o_count) return false;
        return true;
    }
};

class Solution {
    private boolean win(String[] board, char player) {
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(0) == player && board[i].charAt(1) == player && board[i].charAt(2) == player)
                return true;
            if (board[0].charAt(i) == player && board[1].charAt(i) == player && board[2].charAt(i) == player)
                return true;
        }
        if (board[0].charAt(0) == player && board[1].charAt(1) == player && board[2].charAt(2) == player)
            return true;
        if (board[0].charAt(2) == player && board[1].charAt(1) == player && board[2].charAt(0) == player)
            return true;
        return false;
    }

    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                if (c == 'X') xCount++;
                else if (c == 'O') oCount++;
            }
        }
        if (oCount > xCount || xCount - oCount > 1) return false;
        boolean xWin = win(board, 'X');
        boolean oWin = win(board, 'O');
        if (xWin && oWin) return false;
        if (xWin && xCount != oCount + 1) return false;
        if (oWin && xCount != oCount) return false;
        return true;
    }
}

var validTicTacToe = function(board) {
    function win(player) {
        for (let i = 0; i < 3; i++) {
            if (board[i][0] === player && board[i][1] === player && board[i][2] === player)
                return true;
            if (board[0][i] === player && board[1][i] === player && board[2][i] === player)
                return true;
        }
        if (board[0][0] === player && board[1][1] === player && board[2][2] === player)
            return true;
        if (board[0][2] === player && board[1][1] === player && board[2][0] === player)
            return true;
        return false;
    }

    let xCount = 0, oCount = 0;
    for (let row of board) {
        for (let c of row) {
            if (c === 'X') xCount++;
            else if (c === 'O') oCount++;
        }
    }
    if (oCount > xCount || xCount - oCount > 1) return false;
    let xWin = win('X');
    let oWin = win('O');
    if (xWin && oWin) return false;
    if (xWin && xCount !== oCount + 1) return false;
    if (oWin && xCount !== oCount) return false;
    return true;
};

Problem Description

You are given a 3x3 Tic-Tac-Toe board, represented as an array of strings board, where each string is a row of the board. Each cell contains either 'X', 'O', or a space ' ' (for empty). You must determine if the given board state is a valid Tic-Tac-Toe state.

'X' always goes first, and players alternate turns.
The number of 'X' is always equal to or exactly one more than the number of 'O'.
Once a player has won, no further moves are allowed.
There can never be both an 'X' and 'O' win at the same time.

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

Thought Process

To determine if a Tic-Tac-Toe board is valid, we need to check more than just the number of 'X' and 'O'. We must ensure that the game rules are followed: 'X' starts, players alternate, and once there is a winner, the game stops.

A brute-force approach might try to simulate every possible game, but that's inefficient and unnecessary. Instead, we can use the properties of the board: count of each symbol, and check for win conditions. If the counts or win states violate the rules, the board is invalid.

The trickiest part is handling cases where both players appear to have won, or where the move counts don't match the winner. We need to carefully examine all winning lines and the move counts to validate the state.

Solution Approach

Step 1: Count the number of 'X' and 'O' on the board.
- The count of 'O' should never exceed 'X'.
- The count of 'X' should never be more than one greater than 'O'.
Step 2: Check if either player has won.
- For each row, column, and diagonal, check if all three cells are the same and not empty.
- Record if 'X' or 'O' has a winning line.
Step 3: Validate win and move counts.
- If both 'X' and 'O' win, the board is invalid.
- If 'X' wins, 'X' must have one more move than 'O'.
- If 'O' wins, 'X' and 'O' must have the same number of moves.
Step 4: If all checks pass, the board is valid.

This approach ensures we check all the essential rules efficiently, using simple counting and line checks.

Example Walkthrough

Consider the board:

  ["XOX",
   " X ",
   "   "]

Count 'X': 3; Count 'O': 1
Check win:
- No row, column, or diagonal has three of the same non-empty symbol.
Is the count valid? 3 - 1 = 2 (should be 0 or 1). So, invalid state.

Another example:

  ["XOX",
   "O O",
   "XOX"]

Count 'X': 5; Count 'O': 4
Check win:
- No winning line for either player.
Is the count valid? 5 - 4 = 1 (valid).
No win, counts valid → valid state.

Time and Space Complexity

Brute-force approach: Simulating all possible games is exponential and impractical.
Optimized approach (our solution):
- Counting symbols: O(1) (since the board is always 3x3).
- Checking win conditions: O(1) (fixed number of rows, columns, diagonals).
- Total Time Complexity: O(1).
- Space Complexity: O(1), no extra space used except a few variables.

Summary

To validate a Tic-Tac-Toe board, we count the number of moves for each player, check for any winning lines, and ensure that the move counts and win states are consistent with the game rules. This approach is efficient (constant time and space), avoids unnecessary simulation, and is robust against tricky edge cases. The elegance comes from reducing the problem to counting and simple line checks, using the fixed size of the board to our advantage.

AlgoMap.io

Want Help Cracking FAANG?