LeetCode 794: Valid Tic-Tac-Toe State Solution

Master LeetCode problem 794 (Valid Tic-Tac-Toe State), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

794. Valid Tic-Tac-Toe State

Medium

Array Matrix

Problem Explanation

Explanation

To determine if a given Tic-Tac-Toe board is valid, we need to check if the board configuration is reachable during a valid game. We can do this by considering the following conditions:

The number of 'X's is either equal to the number of 'O's or one more than the number of 'O's.
If 'X' wins, then the number of 'X's should be one more than the number of 'O's.
If 'O' wins, then the number of 'X's should be equal to the number of 'O's.
If the game is still in progress, the number of 'X's should either be equal to the number of 'O's or one more than the number of 'O's.

We can iterate through the board to count the number of 'X's and 'O's, and then apply the above conditions to determine if the board is valid.

Solution Code

class Solution {
    public boolean validTicTacToe(String[] board) {
        int numX = 0, numO = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                if (c == 'X') {
                    numX++;
                } else if (c == 'O') {
                    numO++;
                }
            }
        }
        
        if (numX < numO || numX > numO + 1) {
            return false;
        }
        
        boolean xWin = checkWin(board, 'X');
        boolean oWin = checkWin(board, 'O');
        
        if (xWin && numX != numO + 1) {
            return false;
        }
        
        if (oWin && numX != numO) {
            return false;
        }
        
        return true;
    }
    
    private boolean checkWin(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; // Check rows
            }
            if (board[0].charAt(i) == player && board[1].charAt(i) == player && board[2].charAt(i) == player) {
                return true; // Check columns
            }
        }
        
        if (board[0].charAt(0) == player && board[1].charAt(1) == player && board[2].charAt(2) == player) {
            return true; // Check diagonal
        }
        if (board[0].charAt(2) == player && board[1].charAt(1) == player && board[2].charAt(0) == player) {
            return true; // Check diagonal
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 794 (Valid Tic-Tac-Toe State)?

This page provides optimized solutions for LeetCode problem 794 (Valid Tic-Tac-Toe State) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 794 (Valid Tic-Tac-Toe State)?

The time complexity for LeetCode 794 (Valid Tic-Tac-Toe State) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 794 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 794 in Java, C++, or Python.

Back to LeetCode Solutions