Find Tic Tac Toe Winner

XXX. Find Winner on a Tic Tac Toe Game

Array

Simulation

Problem Statement:

Given a series of moves on a Tic Tac Toe board, determine the winner of the game or the game's state. Players take turns making moves, with Player A starting first. The result can be:

• "A": Player A wins.
• "B": Player B wins.
• "Draw": If all cells are filled but there's no winner.
• "Pending": If there are empty cells and no winner yet.

The board size is fixed at 3x3.

Algorithm:

1. Initialize two arrays A and B of size 8 to track moves for Player A and Player B:
   • Indices 0–2 track rows.
   • Indices 3–5 track columns.
   • Index 6 tracks the main diagonal.
   • Index 7 tracks the anti-diagonal.
2. Iterate through the moves:
   • Determine the current player (A or B) based on the turn index.
   • Update the respective row, column, or diagonal counters for the current player.
3. Check if any player has filled a row, column, or diagonal (value equals 3). If so, return the winner.
4. If no winner is found, check if the board is full:
   • If all cells are filled, return "Draw".
   • Otherwise, return "Pending".

Complexity:

Time: O(n), where n is the number of moves.
Space: O(1), as only fixed arrays of size 8 are used.

Java Implementation:

public String tictactoe(int[][] moves) {
    int[] A = new int[8], B = new int[8]; // 3 rows, 3 cols, 2 diagonals for each player

    for (int i = 0; i < moves.length; i++) {
        int r = moves[i][0], c = moves[i][1];
        int[] player = (i % 2 == 0) ? A : B; // Alternate turns between A and B

        player[r]++;         // Increment row count
        player[c + 3]++;     // Increment column count (offset by 3 for columns)
        if (r == c) player[6]++;   // Increment main diagonal
        if (r == 2 - c) player[7]++; // Increment anti-diagonal
    }

    for (int i = 0; i < 8; i++) { // Check if any line is complete
        if (A[i] == 3) return "A";
        if (B[i] == 3) return "B";
    }

    return moves.length == 9 ? "Draw" : "Pending"; // Return Draw or Pending based on moves
}
                

Python Implementation:

def tictactoe(moves):
    A = [0] * 8
    B = [0] * 8

    for i, (r, c) in enumerate(moves):
        player = A if i % 2 == 0 else B
        player[r] += 1
        player[c + 3] += 1
        if r == c:
            player[6] += 1
        if r + c == 2:
            player[7] += 1

    for i in range(8):
        if A[i] == 3:
            return "A"
        if B[i] == 3:
            return "B"

    return "Draw" if len(moves) == 9 else "Pending"
                

C++ Implementation:

string tictactoe(vector>& moves) {
    vector A(8, 0), B(8, 0);

    for (int i = 0; i < moves.size(); ++i) {
        int r = moves[i][0], c = moves[i][1];
        vector& player = (i % 2 == 0) ? A : B;
        player[r]++;
        player[c + 3]++;
        if (r == c)
            player[6]++;
        if (r + c == 2)
            player[7]++;
    }

    for (int i = 0; i < 8; ++i) {
        if (A[i] == 3)
            return "A";
        if (B[i] == 3)
            return "B";
    }

    return moves.size() == 9 ? "Draw" : "Pending";
}