Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1275. Find Winner on a Tic Tac Toe Game - Leetcode Solution

Code Implementation

class Solution:
    def tictactoe(self, moves):
        board = [[0]*3 for _ in range(3)]
        for idx, (r, c) in enumerate(moves):
            player = 1 if idx % 2 == 0 else 2  # 1 for A, 2 for B
            board[r][c] = player

        def check(player):
            # Check rows and columns
            for i in range(3):
                if all(board[i][j] == player for j in range(3)):
                    return True
                if all(board[j][i] == player for j in range(3)):
                    return True
            # Check diagonals
            if all(board[i][i] == player for i in range(3)):
                return True
            if all(board[i][2-i] == player for i in range(3)):
                return True
            return False

        if check(1):
            return "A"
        if check(2):
            return "B"
        if len(moves) == 9:
            return "Draw"
        return "Pending"
      
class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        vector<vector<int>> board(3, vector<int>(3, 0));
        for (int i = 0; i < moves.size(); ++i) {
            int r = moves[i][0], c = moves[i][1];
            int player = (i % 2 == 0) ? 1 : 2;
            board[r][c] = player;
        }
        auto check = [&](int player) {
            for (int i = 0; i < 3; ++i) {
                if (board[i][0] == player && board[i][1] == player && board[i][2] == player)
                    return true;
                if (board[0][i] == player && board[1][i] == player && board[2][i] == player)
                    return true;
            }
            if (board[0][0] == player && board[1][1] == player && board[2][2] == player)
                return true;
            if (board[0][2] == player && board[1][1] == player && board[2][0] == player)
                return true;
            return false;
        };
        if (check(1)) return "A";
        if (check(2)) return "B";
        if (moves.size() == 9) return "Draw";
        return "Pending";
    }
};
      
class Solution {
    public String tictactoe(int[][] moves) {
        int[][] board = new int[3][3];
        for (int i = 0; i < moves.length; i++) {
            int r = moves[i][0], c = moves[i][1];
            int player = (i % 2 == 0) ? 1 : 2;
            board[r][c] = player;
        }
        if (check(board, 1)) return "A";
        if (check(board, 2)) return "B";
        if (moves.length == 9) return "Draw";
        return "Pending";
    }
    private boolean check(int[][] board, int player) {
        for (int i = 0; i < 3; i++) {
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player)
                return true;
            if (board[0][i] == player && board[1][i] == player && board[2][i] == player)
                return true;
        }
        if (board[0][0] == player && board[1][1] == player && board[2][2] == player)
            return true;
        if (board[0][2] == player && board[1][1] == player && board[2][0] == player)
            return true;
        return false;
    }
}
      
var tictactoe = function(moves) {
    const board = Array.from({length: 3}, () => Array(3).fill(0));
    for (let i = 0; i < moves.length; i++) {
        const [r, c] = moves[i];
        const player = i % 2 === 0 ? 1 : 2;
        board[r][c] = player;
    }
    const check = (player) => {
        for (let i = 0; i < 3; i++) {
            if (board[i][0] === player && board[i][1] === player && board[i][2] === player)
                return true;
            if (board[0][i] === player && board[1][i] === player && board[2][i] === player)
                return true;
        }
        if (board[0][0] === player && board[1][1] === player && board[2][2] === player)
            return true;
        if (board[0][2] === player && board[1][1] === player && board[2][0] === player)
            return true;
        return false;
    }
    if (check(1)) return "A";
    if (check(2)) return "B";
    if (moves.length === 9) return "Draw";
    return "Pending";
};

Problem Description

Given a list of moves for a 3x3 Tic Tac Toe game, determine the result of the game. Each move is represented as a pair [row, col], and the moves are made in order, alternating between Player A and Player B. Player A always moves first. The game can end in one of the following ways:
  • "A" if Player A wins
  • "B" if Player B wins
  • "Draw" if all cells are filled and there is no winner
  • "Pending" if the game is not yet finished and there is no winner
The input is a list moves of length at most 9, where each element is a list [row, col] representing a move. Each cell is used at most once, and all moves are valid.

Thought Process

To solve this problem, we need to simulate the Tic Tac Toe game based on the given sequence of moves. The key is to track the state of the board after each move and check for a win condition after all moves are made. A brute-force approach would involve checking every row, column, and diagonal after every move, but we can optimize by only checking after all moves are played, since the input size is very small (maximum 9 moves). We also need to alternate between players and ensure the result is returned according to the rules.

Solution Approach

The solution involves the following steps:
  1. Initialize the Board: Create a 3x3 grid to represent the Tic Tac Toe board. Each cell starts as empty (e.g., 0).
  2. Apply Moves: Iterate through the moves list. For each move, determine which player's turn it is (Player A on even indices, Player B on odd indices) and mark the corresponding cell in the board.
  3. Check for Win: After all moves are applied, check if either player has completed a row, column, or diagonal. This is done by checking all rows, columns, and both diagonals for three matching marks from the same player.
  4. Determine the Result:
    • If Player A has a winning line, return "A".
    • If Player B has a winning line, return "B".
    • If all cells are filled (9 moves), return "Draw".
    • Otherwise, return "Pending" (the game is not yet finished).
This approach is efficient because the board is small and checking all win conditions is fast.

Example Walkthrough

Let's consider the following input: 
  moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Step-by-step:
  • Move 0: Player A marks (0,0)
  • Move 1: Player B marks (2,0)
  • Move 2: Player A marks (1,1)
  • Move 3: Player B marks (2,1)
  • Move 4: Player A marks (2,2)
The board now looks like: 
  A |   |  
  --+---+--
    | A |  
  --+---+--
  B | B | A
Now, check for a winner:
  • Player A has a diagonal: (0,0), (1,1), (2,2)
  • So, the result is "A"

Time and Space Complexity

  • Brute-force approach: For each move, check all rows, columns, and diagonals. Since there are at most 9 moves and 8 possible lines (3 rows, 3 columns, 2 diagonals), this is O(1) due to the small, constant board size.
  • Optimized approach (as above): We only check for a win after all moves are made, which is still O(1). Space complexity is also O(1) for the 3x3 board.
The problem is inherently small, so both time and space costs are negligible.

Summary

The solution simulates the Tic Tac Toe game by marking each move on a grid and checking all possible winning lines after the moves are played. The approach is simple and efficient due to the fixed small size of the board. By alternating player turns and checking for a winner only once, the code remains clean and easy to understand. This makes the solution both elegant and robust for all valid inputs.