Table of Contents

## Problem Statement

Valid Tic-Tac-Toe State LeetCode Solution – We are given a Tic-Tac-Toe board as a string array board & are asked to return true iff 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’, & ‘O’. The ‘ ‘ character represents an empty square.

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.

**Constraints:**

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

## Examples & Explanations

**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 Explanation: This state of game is achievable.

## Approach

The approach discussed here is brute force, it is easy to implement if edge cases are begin taken care of. Let’s call player marking X, playerX and player marking O, playerO. We know that playerX wins if 3 X’s are marked on the board either row-wise or col-wise or diagonal-wise or anti-diagonal-wise, & similarly with playerO.

We will use variables rows & cols of size 3 to keep the count of X’s and O’s. For every X marked in row i and column j, we will increment the value of rows[i] and cols[j] by 1and for every O marked, we will decrement the value by 1. Use another variable diag and antiDiag to keep track of diagonal & anti-diagonal marked char. Increment by 1 diag if X is marked and decrement by 1 otherwise.

To know if players have played their turns at their chances, keep a variable turn, which increases by 1 when X is marked and decreases by 1 otherwise. Since playerX starts the game, the value of turn can be 0 or 1.

Then we will check all the necessary conditions like –

- only one player can win
- turn == 0 or 1, if not return false
- playerX wins but turn ≠ 1 ⇒ not possible
- playerO wins but turn ≠ 0 ⇒ not possible

## Code

### C++ code for **Valid Tic-Tac-Toe State**

class Solution { public: bool validTicTacToe(vector<string>& board) { int rows[3]={0,0,0}, cols[3]={0,0,0}, diag=0, antiDiag=0, turns=0; for(int i=0; i<3; i++) { for(int j=0; j<3; j++) { if(board[i][j] == 'X') { rows[i]++; cols[j]++; if(i==j) diag++; if(i+j == 2) antiDiag++; turns++; } else if(board[i][j] == 'O') { rows[i]--; cols[j]--; if(i==j) diag--; if(i+j == 2) { antiDiag--; } turns--; } } } bool Xwins = rows[0] == 3 || rows[1] == 3 || rows[2] == 3 || cols[0] == 3 || cols[1] == 3 || cols[2] == 3 || diag == 3 || antiDiag == 3; bool Owins = rows[0] == -3 || rows[1] == -3 || rows[2] == -3 || cols[0] == -3 || cols[1] == -3 || cols[2] == -3 || diag == -3 || antiDiag == -3; if ((Xwins && turns != 1) || (Owins && turns != 0)) return 0; if(Xwins && Owins) return 0; return (turns == 0 || turns == 1); } };

### Java code for **Valid Tic-Tac-Toe State**

class Solution { public boolean validTicTacToe(String[] board) { int turns = 0; int[] rows = new int[3]; int[] cols = new int[3]; int diag = 0; int antiDiag = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (board[i].charAt(j) == 'X') { turns++; rows[i]++; cols[j]++; if (i == j) diag++; if (i + j == 2) antiDiag++; } else if (board[i].charAt(j) == 'O') { turns--; rows[i]--; cols[j]--; if (i == j) diag--; if (i + j == 2) antiDiag--; } } } boolean Xwins = false; Xwins = rows[0] == 3 || rows[1] == 3 || rows[2] == 3 || cols[0] == 3 || cols[1] == 3 || cols[2] == 3 || diag == 3 || antiDiag == 3; boolean Owins = false; Owins = rows[0] == -3 || rows[1] == -3 || rows[2] == -3 || cols[0] == -3 || cols[1] == -3 || cols[2] == -3 || diag == -3 || antiDiag == -3; if ((Xwins && turns != 1) || (Owins && turns != 0)) return false; if(Xwins && Owins) return false; return (turns == 0 || turns == 1); } }

## Complexity Analysis for Valid Tic-Tac-Toe State LeetCode Solution

- Time complexity: O(1)
- Loops in the algorithm run for constant time i.e. 3

- Space complexity: O(1)
- arrays “rows” and “cols” are of constant size