Find Winner on a Tic Tac Toe Game

LeetCode 1400 | Difficulty: Easy

Easy

Problem Description

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

- Players take turns placing characters into empty squares `' '`.

- The first player `A` always places `'X'` characters, while the second player `B` always places `'O'` characters.

- `'X'` and `'O'` characters are always placed into empty squares, never on 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.

Given a 2D integer array moves where moves[i] = [row~i~, col~i~] indicates that the i^th move will be played on grid[row~i~][col~i~]. return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.

Constraints:

- `1 <= moves.length <= 9`

- `moves[i].length == 2`

- `0 <= row~i~, col~i~ <= 2`

- There are no repeated elements on `moves`.

- `moves` follow the rules of tic tac toe.

Topics: Array, Hash Table, Matrix, Simulation

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 108 ms)

Metric	Value
Runtime	108 ms
Memory	24 MB
Date	2019-12-06

Solution

public class Solution {
    public string Tictactoe(int[][] moves) {
    char[,] board = new char[3, 3];
    bool isP1 = true;
    for (int i = 0; i < moves.Length; i++)
    {
        var move = moves[i];
        board[move[0], move[1]] = isP1 ? 'X' : 'O';
        isP1 = isP1 ^ true;
    }

    char winnerMove = '.';
    for (int i = 0; i < 3; i++)
    {
        if (board[i, 0] == board[i, 1] && board[i, 1] == board[i, 2])
            winnerMove = board[i, 0];
        if (board[0, i] == board[1, i] && board[1, i] == board[2, i])
            winnerMove = board[0, i];
    }

    if (board[0, 0] == board[1, 1] && board[1, 1] == board[2, 2])
    {
        winnerMove = board[0, 0];
    }

    if (board[0, 2] == board[1, 1] && board[1, 1] == board[2, 0])
    {
        winnerMove = board[0, 2];
    }

    return winnerMove == 'X' ? "A" : winnerMove == 'O' ? "B" : winnerMove == '.' && moves.Length == 9 ? "Draw" : "Pending";
    }
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: It's straightforward to check if A or B won or not, check for each row/column/diag if all the three are the same.

Hint 2: Then if no one wins, the game is a draw iff the board is full, i.e. moves.length = 9 otherwise is pending.