Reference: LeetCode

Difficulty: Medium

## Problem

A Tic-Tac-Toe board is given 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, and 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 3 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 | // "X" goes first, then "O" goes next! |

## Analysis

### Naive

Necessary conditions for a tic-tac-toe board to be valid:

- Since players take turns and
`X`

goes first. The number of`X`

‘s must be equal to or one greater than the number of`O`

. - A player that wins has to win on the move that they take:
- If
`X`

wins, the number of`X`

is one more than the number of`O`

. - If
`O`

wins, the number of`X`

is equal to the number of`O`

.

- If
- The board can’t simultaneously have three
`X`

s and three`O`

s in a row, since once one player has won (on their move), there are no subsequent moves.

**We check these conditions in reverse.** In any board, one player, or both players have won.

1 | public boolean validTicTacToe(String[] board) { |

**Time:** $O(1)$**Space:** $O(1)$

Comment