Find Winner on a Tic Tac Toe Game
On this page 
Problem Statement
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.
Input:
A 2D integer array
moves, wheremoves[i] = [rowi, coli]specifies the position of the ith move on the grid.
Assumptions:
The moves are valid and adhere to the rules of Tic-Tac-Toe.
The grid starts empty, and player A always plays first.
Example 1
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Example 2
Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Example 3
Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Constraints
Solution 1: Winning Strategies for Tic-Tac-Toe: A Grid-Based Approach
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 tonullto represent empty spaces for the Tic-Tac-Toe game.Player Move Recording: The function iterates through the
playerMovesarray, 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.
Solution 2: Using a Hash Map
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 findTicTacToeWinnerUsingHashMapfunction 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.
Solution 3: Using another grid based approach
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,
playerXMovesandplayerOMoves, 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.
Solution 4: Using another grid based approach
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.
Solution 5: Evaluating Tic-Tac-Toe Outcomes Using Geometric Principles
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.
Solution 6: Efficient Winner Detection in Tic-Tac-Toe Using 1D Array Representation
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
1and 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).
Solution 7: Tic-Tac-Toe using Breadth-First Search (BFS)
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.
Frequently asked questions
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