Find Winner on a Tic Tac Toe Game

Easy
304.

Find Winner on a Tic Tac Toe Game

Find Winner on a Tic Tac Toe Game is an easy coding problem on arrays, hash table and matrix, asked in Amazon, Microsoft and Adobe interviews.

Two players take turns on a 3 × 3 grid. A always moves first and places X; B places O. moves[i] = [row, col] is the cell claimed on the i-th turn, and no cell is claimed twice.

Return "A" or "B" if that player has three in a row (horizontally, vertically or diagonally), "Draw" if all nine cells are filled with no winner, and "Pending" if the game is unfinished.

Example 1

Input
moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output
A
Explanation
A holds the main diagonal.

Example 2

Input
moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output
B
Explanation
B holds the anti-diagonal.

Example 3

Input
moves = [[0,0],[1,1]]
Output
Pending

Constraints

  • 1 <= moves.length <= 9
  • moves[i].length == 2
  • 0 <= moves[i][j] <= 2
  • No cell is claimed twice.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} moves
 * @return {string}
 */
var tictactoe = function(moves) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Winner on a Tic Tac Toe Game — Problem & Solution

Find Winner on a Tic Tac Toe Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Winner on a Tic Tac Toe Game is an easy coding problem on arrays, hash table and matrix, asked in Amazon, Microsoft and Adobe interviews.

Problem statement

Two players take turns on a 3 × 3 grid. A always moves first and places X; B places O. moves[i] = [row, col] is the cell claimed on the i-th turn, and no cell is claimed twice.

Return "A" or "B" if that player has three in a row (horizontally, vertically or diagonally), "Draw" if all nine cells are filled with no winner, and "Pending" if the game is unfinished.

Example 1

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: A
Explanation: A holds the main diagonal.

Example 2

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: B
Explanation: B holds the anti-diagonal.

Example 3

Input: moves = [[0,0],[1,1]]
Output: Pending

Constraints

  • 1 <= moves.length <= 9
  • moves[i].length == 2
  • 0 <= moves[i][j] <= 2
  • No cell is claimed twice.

Hints for Find Winner on a Tic Tac Toe Game

  1. Hint 1

    Replay the moves onto a 3 × 3 board — even moves belong to A, odd moves to B.

  2. Hint 2

    Then check the eight lines: three rows, three columns and two diagonals.

  3. Hint 3

    Only after finding no winner does the move count decide between Draw and Pending.

How to solve Find Winner on a Tic Tac Toe Game

Replay the moves onto a 3 × 3 board (even turns are A), then test the eight winning lines; only if none wins does the move count decide Draw versus Pending.

Approach

  1. Fill board[r][c] with 1 for A's moves and 2 for B's.
  2. For each of the 3 rows, 3 columns and 2 diagonals, check for three equal non-zero cells.
  3. Return the winner, else "Draw" if 9 moves were played, else "Pending".

Why it works

A finished line is the only win condition, and since moves alternate with A first, the parity of the move index identifies the player.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • Check for a winner before declaring a draw — a game can be won on the ninth move.

Reference solution

Python

def tictactoe(moves) -> str:
    board = [[0] * 3 for _ in range(3)]
    for i, (r, c) in enumerate(moves):
        board[r][c] = 1 if i % 2 == 0 else 2
    lines = [
        [(0, 0), (0, 1), (0, 2)], [(1, 0), (1, 1), (1, 2)], [(2, 0), (2, 1), (2, 2)],
        [(0, 0), (1, 0), (2, 0)], [(0, 1), (1, 1), (2, 1)], [(0, 2), (1, 2), (2, 2)],
        [(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)],
    ]
    for line in lines:
        a, b, c = line
        v = board[a[0]][a[1]]
        if v != 0 and v == board[b[0]][b[1]] and v == board[c[0]][c[1]]:
            return "A" if v == 1 else "B"
    return "Draw" if len(moves) == 9 else "Pending"

Java

public static String tictactoe(int[][] moves) {
    int[][] board = new int[3][3];
    for (int k = 0; k < moves.length; k++) {
        board[moves[k][0]][moves[k][1]] = k % 2 == 0 ? 1 : 2;
    }
    int[][][] lines = {
        {{0, 0}, {0, 1}, {0, 2}}, {{1, 0}, {1, 1}, {1, 2}}, {{2, 0}, {2, 1}, {2, 2}},
        {{0, 0}, {1, 0}, {2, 0}}, {{0, 1}, {1, 1}, {2, 1}}, {{0, 2}, {1, 2}, {2, 2}},
        {{0, 0}, {1, 1}, {2, 2}}, {{0, 2}, {1, 1}, {2, 0}}
    };
    for (int[][] line : lines) {
        int v = board[line[0][0]][line[0][1]];
        if (v != 0 && v == board[line[1][0]][line[1][1]] && v == board[line[2][0]][line[2][1]]) {
            return v == 1 ? "A" : "B";
        }
    }
    return moves.length == 9 ? "Draw" : "Pending";
}

C++

string tictactoe(vector<vector<int>>& moves) {
    int board[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
    for (int k = 0; k < (int) moves.size(); k++) {
        board[moves[k][0]][moves[k][1]] = k % 2 == 0 ? 1 : 2;
    }
    int lines[8][3][2] = {
        {{0, 0}, {0, 1}, {0, 2}}, {{1, 0}, {1, 1}, {1, 2}}, {{2, 0}, {2, 1}, {2, 2}},
        {{0, 0}, {1, 0}, {2, 0}}, {{0, 1}, {1, 1}, {2, 1}}, {{0, 2}, {1, 2}, {2, 2}},
        {{0, 0}, {1, 1}, {2, 2}}, {{0, 2}, {1, 1}, {2, 0}}
    };
    for (int i = 0; i < 8; i++) {
        int v = board[lines[i][0][0]][lines[i][0][1]];
        if (v != 0 && v == board[lines[i][1][0]][lines[i][1][1]] && v == board[lines[i][2][0]][lines[i][2][1]]) {
            return v == 1 ? "A" : "B";
        }
    }
    return moves.size() == 9 ? "Draw" : "Pending";
}

JavaScript

var tictactoe = function(moves) {
    const board = [];
    for (let r = 0; r < 3; r++) board.push(new Array(3).fill(0));
    for (let i = 0; i < moves.length; i++) {
        board[moves[i][0]][moves[i][1]] = i % 2 === 0 ? 1 : 2;
    }
    const lines = [
        [[0, 0], [0, 1], [0, 2]], [[1, 0], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]],
        [[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 1], [2, 1]], [[0, 2], [1, 2], [2, 2]],
        [[0, 0], [1, 1], [2, 2]], [[0, 2], [1, 1], [2, 0]]
    ];
    for (let i = 0; i < lines.length; i++) {
        const line = lines[i];
        const v = board[line[0][0]][line[0][1]];
        if (v !== 0 && v === board[line[1][0]][line[1][1]] && v === board[line[2][0]][line[2][1]]) {
            return v === 1 ? "A" : "B";
        }
    }
    return moves.length === 9 ? "Draw" : "Pending";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets