The question doesn’t really require any Data Structure or Algorithmic knowledge. It only requires you to sit down and observe a 3x3 tic-tac-toe board to find out the minimum number of conditions you would have to check to know that it’s a valid state. Let’s look at some conditions:
- Clearly, number of X >= number of O because X takes the first turn
- At the same time, number of X - number of O cannot exceed 1 as they play turn by turn
- X or O cannot win the game twice, that is:
- 2 rows cannot be “XXX” or “OOO”. Note that this is not a valid state as per condition 2 so we don’t have to consider this.
- 2 columns cannot be “XXX” or “OOO”. Note that this is not a valid state as per condition 2 so we don’t have to consider this.\
- Both diagonals cannot contain only “X” or only “O”. Actually, this condition is wrong! Both diagonals can be filled with only X or only O. Consider this valid state:
X O X X O X O O -> O X O X O X X O X
- Both “X” and “O” cannot win the game, that is:
- If one row is “XXX”, any other cannot be “OOO”
- If one column is “XXX”, the other cannot be “OOO”
- If X has won the game then number of X should be equal to number of O - 1 (as O doesn’t get to play the next chance)
- If O has won the game then number of X should be equal to number of O (as X doesn’t get to play the next chance)
Note that the condition 3 above is contained in all others so we do not need to check that.
bool validTicTacToe(vector<string>& board) {
bool xWon = false, oWon = false;
int numX = 0, numO = 0;
// check rows
for (string s : board) {
if (s=="XXX")
xWon=true;
if (s=="OOO")
oWon = true;
for (char c : s) {
if (c=='X')
numX++;
else if (c=='O')
numO++;
}
}
// conditions 1, 2 and 4
if (numO>numX || numX-numO>1 || (xWon && oWon))
return false;
// check columns
for (int j=0; j<3; j++) {
string temp = "";
for (int i=0; i<3; i++) {
temp+=board[i][j];
}
if (temp == "XXX")
xWon = true;
if (temp == "OOO")
oWon = true;
}
// check diagonals
if (board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X')
xWon = true;
if (board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O')
oWon = true;
if (board[0][2] == 'X' && board[1][1] == 'X' && board[2][0] == 'X')
xWon = true;
if (board[0][2] == 'O' && board[1][1] == 'O' && board[2][0] == 'O')
oWon = true;
// condition 4
if (xWon && oWon)
return false;
// condition 5
if (xWon && numX-numO==0)
return false;
// condition 6
if (oWon && numX-numO==1)
return false;
return true;
}
Time complexity: O(1) as the board is of constant size (3x3)