Problem Statement Solution 1: Winning Strategies for Tic-Tac-Toe: A Grid-Based Approach Solution 2: Using a Hash Map Solution 3: Using another grid based approach Solution 4: Using another grid based approach Solution 5: Evaluating Tic-Tac-Toe Outcomes Using Geometric Principles Solution 6: Efficient Winner Detection in Tic-Tac-Toe Using 1D Array Representation Solution 7: Tic-Tac-Toe using Breadth-First Search (BFS) Frequently asked questions More Problems Solutions

Tic-Tac-Toe is a strategic game played on a 3x3 grid between two players, A and B. The rules are as follows:

**Players**:Player A uses the symbol 'X'.

Player B uses the symbol 'O'.

**Gameplay**:Players alternate turns, placing their symbols in unoccupied squares on the grid.

Moves can only be made in empty squares.

**Winning Conditions**:The game concludes when one player achieves three of their symbols in a row—either horizontally, vertically, or diagonally.

If all squares are filled without a winner, the game ends in a draw.

**Game States**:**Winner**: Return 'A' if player A wins, or 'B' if player B wins.**Draw**: Return "Draw" if the game ends with no available moves and no winner has been determined.**Pending**: Return "Pending" if there are still moves left to be played and no winner has emerged.

A 2D integer array

`moves`

, where`moves[i] = [rowi, coli]`

specifies the position of the ith move on the grid.

The moves are valid and adhere to the rules of Tic-Tac-Toe.

The grid starts empty, and player A always plays first.

**Input: **moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]

**Output: **"A"

**Input: **moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]

**Output: **"B"

**Input: **moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]

**Output: **"Draw"

```
function determineTicTacToeWinnerGridApproach (playerMoves) {
let gameBoard = new Array(3).fill().map(() => Array(3).fill(null));
for (let i = 0; i < playerMoves.length; i += 2) {
gameBoard[playerMoves[i][0]][playerMoves[i][1]] = "A"; // Player A's move
}
for (let i = 1; i < playerMoves.length; i += 2) {
gameBoard[playerMoves[i][0]][playerMoves[i][1]] = "B"; // Player B's move
}
// Check rows for a winner
for (let row = 0; row < 3; row++) {
if (gameBoard[row][0] != null &&
gameBoard[row][0] === gameBoard[row][1] &&
gameBoard[row][0] === gameBoard[row][2]) {
return gameBoard[row][0];
}
}
// Check columns for a winner
for (let col = 0; col < 3; col++) {
if (gameBoard[0][col] != null &&
gameBoard[0][col] === gameBoard[1][col] &&
gameBoard[0][col] === gameBoard[2][col]) {
return gameBoard[0][col];
}
}
// Check diagonals for a winner
if (gameBoard[0][0] != null &&
gameBoard[0][0] === gameBoard[1][1] &&
gameBoard[0][0] === gameBoard[2][2]) {
return gameBoard[0][0];
}
if (gameBoard[2][0] != null &&
gameBoard[2][0] === gameBoard[1][1] &&
gameBoard[2][0] === gameBoard[0][2]) {
return gameBoard[2][0];
}
// Check for draw or pending
if (playerMoves.length === 9) {
return "Draw";
}
return "Pending";
};
const moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]];
determineTicTacToeWinnerGridApproach(moves1); //output: A
const moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]];
determineTicTacToeWinnerGridApproach(moves2); //output: B
const moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]];
determineTicTacToeWinnerGridApproach(moves3); //output: Draw
```

**Game Board Initialization:**A 3x3 grid (`gameBoard`

) is created and initialized to`null`

to represent empty spaces for the Tic-Tac-Toe game.**Player Move Recording:**The function iterates through the`playerMoves`

array, updating the grid with 'A' for Player A and 'B' for Player B based on their turns.**Winning Condition Checks:**It systematically checks all rows, columns, and diagonals for three matching symbols to determine if a player has won.**Game Outcome Determination:**If no winner is found and all nine moves are played, the function returns "Draw"; otherwise, it returns "Pending" if moves remain.

```
function findTicTacToeWinnerUsingHashMap(moves) {
const board = Array(3).fill(null).map(() => Array(3).fill(''));
const winningCombinations = [
[[0, 0], [0, 1], [0, 2]], // row 1
[[1, 0], [1, 1], [1, 2]], // row 2
[[2, 0], [2, 1], [2, 2]], // row 3
[[0, 0], [1, 0], [2, 0]], // col 1
[[0, 1], [1, 1], [2, 1]], // col 2
[[0, 2], [1, 2], [2, 2]], // col 3
[[0, 0], [1, 1], [2, 2]], // diagonal \
[[0, 2], [1, 1], [2, 0]], // diagonal /
];
for (let i = 0; i < moves.length; i++) {
const [row, col] = moves[i];
board[row][col] = i % 2 === 0 ? 'A' : 'B'; // 'A' for player A, 'B' for player B
}
for (const combo of winningCombinations) {
const [a, b, c] = combo;
if (board[a[0]][a[1]] && board[a[0]][a[1]] === board[b[0]][b[1]] && board[a[0]][a[1]] === board[c[0]][c[1]]) {
return board[a[0]][a[1]];
}
}
return moves.length === 9 ? 'Draw' : 'Pending';
}
const moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]];
findTicTacToeWinnerUsingHashMap(moves1); //output: A
const moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]];
findTicTacToeWinnerUsingHashMap(moves2); //output: B
const moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]];
findTicTacToeWinnerUsingHashMap(moves3); //output: Draw
```

how the `findTicTacToeWinnerUsingHashMap`

function works in bullet points:

**Initialize the Board:**Create a 3x3 grid (array of arrays) filled with empty strings.

**Define Winning Combinations:**List all possible winning combinations (rows, columns, diagonals) as coordinate pairs.

**Record Moves:**Iterate through the list of moves.

For each move, determine which player's turn it is (Player A or Player B).

Update the corresponding position on the board with 'A' or 'B'.

**Check for a Winner:**For each winning combination, check if the same player occupies all three positions.

If a player wins, return that player's symbol ('A' or 'B').

**Determine the Game State:**If no winner is found, check if all 9 moves have been made.

If yes, return "Draw."

If not, return "Pending."

This structure allows the function to efficiently track the game state and identify outcomes based on player moves.

```
function determineTicTacToeOutcomeGridBasedTwo (playerMoves) {
const playerXMoves = [];
const playerOMoves = [];
function checkRows(moves) {
const rowCounts = [0, 0, 0];
moves.forEach(([row, col]) => {
rowCounts[row]++;
});
return rowCounts.includes(3);
}
function checkColumns(moves) {
const colCounts = [0, 0, 0];
moves.forEach(([row, col]) => {
colCounts[col]++;
});
return colCounts.includes(3);
}
function checkDiagonals(moves) {
let leftDiagonalCount = 0, rightDiagonalCount = 0;
moves.forEach(([row, col]) => {
if (row === col) leftDiagonalCount++;
if (row + col === 2) rightDiagonalCount++;
});
return leftDiagonalCount === 3 || rightDiagonalCount === 3;
}
for (let i = 0; i < playerMoves.length; i++) {
if (i % 2 === 0) playerXMoves.push(playerMoves[i]); // Player A (X)
else playerOMoves.push(playerMoves[i]); // Player B (O)
}
if (checkRows(playerXMoves) || checkColumns(playerXMoves) || checkDiagonals(playerXMoves)) return 'A';
if (checkRows(playerOMoves) || checkColumns(playerOMoves) || checkDiagonals(playerOMoves)) return 'B';
if (playerMoves.length === 9) return 'Draw';
return 'Pending';
};
const moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]];
determineTicTacToeOutcomeGridBasedTwo(moves1); //output: A
const moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]];
determineTicTacToeOutcomeGridBasedTwo(moves2); //output: B
const moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]];
determineTicTacToeOutcomeGridBasedTwo(moves3); //output: Draw
```

**Grid Representation of Moves:**The function uses two arrays,`playerXMoves`

and`playerOMoves`

, to store the positions of Player A's and Player B's moves, respectively.**Winning Condition Checks:**It systematically checks for three matching symbols in rows, columns, and diagonals by counting occurrences from the recorded moves.**Clear Logic Structure:**The functions for checking rows, columns, and diagonals are clearly defined, enhancing readability and maintainability of the code.**Outcome Determination:**The function returns the winner ('A' or 'B'), or indicates if the game is a "Draw" or "Pending" based on the number of moves played.

```
function determineTicTacToeOutcomeGridThree (moves) {
let gameBoard = [["", "", ""], ["", "", ""], ["", "", ""]];
function checkWinner(currentPlayer) {
// Horizontal Check
for (let row = 0; row < 3; row++) {
if (gameBoard[row].every(cell => cell === currentPlayer)) {
return currentPlayer;
}
}
// Vertical Check
for (let col = 0; col < 3; col++) {
if (gameBoard.every(row => row[col] === currentPlayer)) {
return currentPlayer;
}
}
// Diagonal Check (Left to Right)
if (gameBoard[0][0] === currentPlayer &&
gameBoard[1][1] === currentPlayer &&
gameBoard[2][2] === currentPlayer) {
return currentPlayer;
}
// Diagonal Check (Right to Left)
if (gameBoard[0][2] === currentPlayer &&
gameBoard[1][1] === currentPlayer &&
gameBoard[2][0] === currentPlayer) {
return currentPlayer;
}
return null; // No winner yet
}
let moveCount = 0;
let currentPlayer = "O";
for (let i = 0; i < moves.length; i++) {
moveCount++;
currentPlayer = currentPlayer === "O" ? "X" : "O"; // Alternate players
const [row, col] = moves[i];
gameBoard[row][col] = currentPlayer;
const winner = checkWinner(currentPlayer);
if (winner) {
return winner === "X" ? "A" : "B"; // Return winner
}
if (moveCount === 9) {
return "Draw"; // All moves played
}
}
return "Pending"; // Game still ongoing
};
const moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]];
determineTicTacToeOutcomeGridThree(moves1); //output: A
const moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]];
determineTicTacToeOutcomeGridThree(moves2); //output: B
const moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]];
determineTicTacToeOutcomeGridThree(moves3); //output: Draw
```

**Grid Representation:**The function uses a 3x3 array (`gameBoard`

) to represent the Tic-Tac-Toe board, storing the moves of players "X" and "O."**Winner Checking Logic:**It defines a dedicated function (`checkWinner`

) that checks for winning conditions across rows, columns, and diagonals using straightforward iteration and comparison.**Player Turn Management:**The function alternates between players using a simple conditional switch, ensuring turns are managed efficiently throughout the game.**Game Outcome Determination:**It returns the winner ("A" for "X" and "B" for "O"), indicates a "Draw" if all moves are played without a winner, or returns "Pending" if the game is still ongoing.

```
function ticTacToeGeometricApproach(playerMoves) {
const totalMoves = playerMoves.length;
for (let start = 0; start < 2; start++) {
const currentWinner = start === 0 ? "A" : "B";
for (let i = start; i < totalMoves; i += 2) {
const [firstMoveRow, firstMoveCol] = playerMoves[i];
for (let j = i + 2; j < totalMoves; j += 2) {
const [secondMoveRow, secondMoveCol] = playerMoves[j];
for (let k = j + 2; k < totalMoves; k += 2) {
const [thirdMoveRow, thirdMoveCol] = playerMoves[k];
// Check if the three moves are collinear
if ((firstMoveRow - secondMoveRow) * (firstMoveCol - thirdMoveCol) ===
(firstMoveRow - thirdMoveRow) * (firstMoveCol - secondMoveCol)) {
return currentWinner;
}
}
}
}
}
return totalMoves === 9 ? "Draw" : "Pending";
};
const moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]];
ticTacToeGeometricApproach(moves1); //output: A
const moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]];
ticTacToeGeometricApproach(moves2); //output: B
const moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]];
ticTacToeGeometricApproach(moves3); //output: Draw
```

**Player Move Tracking:**The function iterates through the moves made by players "A" and "B," alternating between them based on their turn, and stores each move's row and column coordinates.**Collinearity Check:**For each player, it checks combinations of moves to see if any three moves are collinear using a mathematical condition that determines if three points lie on the same line.**Winner Identification:**If three collinear moves are found for a player, the function immediately returns that player's identifier ("A" or "B") as the winner.**Game State Evaluation:**If all nine moves have been made without a winner, the function returns "Draw"; otherwise, it returns "Pending" if the game is still ongoing, based on the number of moves played.

```
function ticTacToeArrayApproach(moves) {
const GOAL_STATES = [ // 8 possible winning combinations
[0, 1, 2], // top row
[3, 4, 5], // middle row
[6, 7, 8], // bottom row
[0, 3, 6], // left column
[1, 4, 7], // middle column
[2, 5, 8], // right column
[0, 4, 8], // diagonal
[2, 4, 6], // diagonal
];
const boardState = Array(9).fill(0); // Represents the board state
let currentPlayer = 1; // 1 for Player A, -1 for Player B
for (const move of moves) {
const [x, y] = move;
boardState[x + 3 * y] = currentPlayer; // Update board state
currentPlayer = -currentPlayer; // Switch players
}
// Check for a winner
for (const player of [-1, 1]) {
for (const combo of GOAL_STATES) {
if (combo.every(index => boardState[index] === player)) {
return player === 1 ? "A" : "B"; // Return winner
}
}
}
// Check for a draw or pending state
return boardState.includes(0) ? "Pending" : "Draw";
};
const moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]];
ticTacToeArrayApproach(moves1); //output: A
const moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]];
ticTacToeArrayApproach(moves2); //output: B
const moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]];
ticTacToeArrayApproach(moves3); //output: Draw
```

**Flat Array Representation:**The board is represented as a single-dimensional array of size 9, where each index corresponds to a position on the Tic-Tac-Toe grid, allowing for efficient tracking of player moves.**Player Switching:**Players are alternated using a simple numeric system, where Player A is represented by`1`

and Player B by`-1`

, enabling straightforward updates to the board state.**Winning Combinations Check:**The function checks all possible winning combinations (rows, columns, and diagonals) after each move to determine if either player has achieved a winning state.**Game State Evaluation:**At the end of the moves, the function assesses whether the game has resulted in a win, a draw (if the board is full), or if it’s still ongoing (if there are empty spaces left).

```
function tictactoeUsingBFS(moves) {
function vertical(x, y) {
if (y + 1 <= 2) {
return [[x, y + 1]];
}
return [];
}
function horizontal(x, y) {
if (x + 1 <= 2) {
return [[x + 1, y]];
}
return [];
}
function diagonal1(x, y) {
if (x + 1 <= 2 && y + 1 <= 2) {
return [[x + 1, y + 1]];
}
return [];
}
function diagonal2(x, y) {
if (x - 1 >= 0 && y + 1 <= 2) {
return [[x - 1, y + 1]];
}
return [];
}
function bfs(moveFunc) {
const seen = new Set();
for (const [y, x] of moves) {
if (seen.has(`${x},${y}`)) continue;
if (x > 0 && y > 0) continue;
const q = [[x, y]];
seen.add(`${x},${y}`);
const player = graph[y][x];
let level = 0;
while (q.length) {
for (let i = 0; i < q.length; i++) {
const [curX, curY] = q.shift();
for (const [xp, yp] of moveFunc(curX, curY)) {
if (graph[yp][xp] === player && !seen.has(`${xp},${yp}`)) {
seen.add(`${xp},${yp}`);
q.push([xp, yp]);
}
}
}
level++;
}
if (level === 3) {
return player;
}
}
}
const graph = [
[null, null, null],
[null, null, null],
[null, null, null]
];
for (let i = 0; i < moves.length; i++) {
const [y, x] = moves[i];
graph[y][x] = i % 2 === 0 ? 'A' : 'B';
}
moves.sort();
return bfs(vertical) || bfs(horizontal) || bfs(diagonal1) || bfs(diagonal2) || (moves.length < 9 ? "Pending" : "Draw");
}
const moves1 = [[0,0],[2,0],[1,1],[2,1],[2,2]];
tictactoeUsingBFS(moves1); //output: A
const moves2 = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]];
tictactoeUsingBFS(moves2); //output: B
const moves3 = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]];
tictactoeUsingBFS(moves3); //output: Draw
```

**Function Purpose**: Determines the outcome of a Tic-Tac-Toe game based on player moves.**Parameters**: Accepts an array of moves, each defined by row and column indices.**Movement Functions**: Defines vertical, horizontal, and diagonal movement checks.**Breadth-First Search (BFS)**: Uses BFS to explore winning paths for each player.**Game State Representation**: Initializes a 3x3 grid to represent the game board and assigns players.**Outcome Evaluation**: Returns "Pending" if moves remain, "Draw" if the board is full, or the winning player.

### What is the best way to solve tic tac toe leetcode game problem?

The fastest approach to solve this problem is using A Grid-Based Approach