794. Valid Tic-Tac-Toe State LeetCode Solution

In this guide, you will get 794. Valid Tic-Tac-Toe State LeetCode Solution with the best time and space complexity. The solution to Valid Tic-Tac-Toe State problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Valid Tic-Tac-Toe State solution in C++
Valid Tic-Tac-Toe State solution in Java
Valid Tic-Tac-Toe State solution in Python
Additional Resources

794. Valid Tic-Tac-Toe State LeetCode Solution image

Problem Statement of Valid Tic-Tac-Toe State

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.

Example 1:

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

Example 2:

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

Example 3:

Input: board = [“XOX”,”O O”,”XOX”]
Output: true

Constraints:

board.length == 3
board[i].length == 3
board[i][j] is either ‘X’, ‘O’, or ‘ ‘.

Complexity Analysis

Time Complexity:
Space Complexity:

794. Valid Tic-Tac-Toe State LeetCode Solution in C++

class Solution {
 public:
  bool validTicTacToe(vector<string>& board) {
    const int countX = sum(board, 'X');
    const int countO = sum(board, 'O');

    if (countX < countO || countX - countO > 1)
      return false;
    if (isWinned(board, 'X') && countX == countO ||
        isWinned(board, 'O') && countX != countO)
      return false;

    return true;
  }

 private:
  int sum(const vector<string>& board, char c) {
    int ans = 0;

    for (const string& row : board)
      ans += ranges::count(row, c);

    return ans;
  }

  bool isWinned(const vector<string>& board, char c) {
    vector<string> rotated = rotate(board);

    auto equalsToThree = [&c](const string& row) {
      return ranges::count(row, c) == 3;
    };

    return ranges::any_of(board, equalsToThree) ||
           ranges::any_of(rotated, equalsToThree) ||
           board[0][0] == c && board[1][1] == c && board[2][2] == c ||
           board[0][2] == c && board[1][1] == c && board[2][0] == c;
  }

  vector<string> rotate(const vector<string>& board) {
    vector<string> rotated(3);

    for (const string& row : board)
      for (int i = 0; i < 3; ++i)
        rotated[i].push_back(row[i]);

    return rotated;
  }
};
/* code provided by PROGIEZ */

794. Valid Tic-Tac-Toe State LeetCode Solution in Java

class Solution {
  public boolean validTicTacToe(String[] board) {
    final int countX = sum(board, 'X');
    final int countO = sum(board, 'O');

    if (countX < countO || countX - countO > 1)
      return false;
    if (isWinned(board, 'X') && countX == countO || //
        isWinned(board, 'O') && countX != countO)
      return false;

    return true;
  }

  private int sum(final String[] board, char c) {
    int ans = 0;

    for (final String row : board)
      ans += row.chars().filter(i -> i == c).count();

    return ans;
  }

  private boolean isWinned(final String[] board, char c) {
    String[] rotated = rotate(board);

    return Arrays.stream(board).anyMatch(row -> row.chars().filter(i -> i == c).count() == 3) ||
        Arrays.stream(rotated).anyMatch(row -> row.chars().filter(i -> i == c).count() == 3) ||
        board[0].charAt(0) == c && board[1].charAt(1) == c && board[2].charAt(2) == c ||
        board[0].charAt(2) == c && board[1].charAt(1) == c && board[2].charAt(0) == c;
  }

  private String[] rotate(final String[] board) {
    String[] rotated = new String[3];

    for (final String row : board)
      for (int i = 0; i < 3; ++i)
        rotated[i] += row.charAt(i);

    return rotated;
  }
}
// code provided by PROGIEZ

794. Valid Tic-Tac-Toe State LeetCode Solution in Python

class Solution:
  def validTicTacToe(self, board: list[str]) -> bool:
    def isWin(c: str) -> bool:
      return (any(row.count(c) == 3 for row in board) or
              any(row.count(c) == 3 for row in list(zip(*board))) or
              all(board[i][i] == c for i in range(3)) or
              all(board[i][2 - i] == c for i in range(3)))

    countX = sum(row.count('X') for row in board)
    countO = sum(row.count('O') for row in board)

    if countX < countO or countX - countO > 1:
      return False
    if isWin('X') and countX == countO or isWin('O') and countX != countO:
      return False

    return True
 # code by PROGIEZ