We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Winner on a Tic Tac Toe Game

Difficulty: Easy

Problem Description

In a Tic-Tac-Toe game played on a 3x3 grid by two players, A and B, you are given a series of moves made by the players. Your task is to determine the winner of the game, if there is one. If the game ends in a draw, return "Draw", and if there are still moves to be played, return "Pending". The first player, A, always plays 'X', while player B plays 'O'.

Key Insights

  • The game can end in three ways: A wins, B wins, or a draw.
  • A win occurs when a player has three of their marks in a row, either horizontally, vertically, or diagonally.
  • The game can still be "Pending" if not all squares are filled and no player has won yet.
  • The maximum number of moves is 9, making exhaustive checking feasible.

Space and Time Complexity

Time Complexity: O(1) - The maximum number of moves is limited to 9, leading to constant time checks. Space Complexity: O(1) - We only need a fixed amount of space for the grid and counters.

Solution

To solve the problem, we can use a 3x3 matrix to represent the game grid. We will iterate through the moves and update the grid accordingly. After each move, we will check for a win condition by inspecting rows, columns, and diagonals. If no winner emerges after all moves, we check if the grid is full to determine if the result is a draw or if it's still pending.

Code Solutions

def tictactoe(moves):
    # Create a 3x3 grid initialized with empty strings
    grid = [['' for _ in range(3)] for _ in range(3)]
    
    for i, move in enumerate(moves):
        row, col = move
        # Determine if current move is A's or B's
        grid[row][col] = 'A' if i % 2 == 0 else 'B'
        
        # Check for a winner after every move
        if check_winner(grid, 'A'):
            return "A"
        if check_winner(grid, 'B'):
            return "B"
    
    # Check if the game is pending or drawn
    if len(moves) < 9:
        return "Pending"
    return "Draw"

def check_winner(grid, player):
    # Check rows, columns and diagonals for a win
    return any(all(cell == player for cell in row) for row in grid) or \
           any(all(grid[i][j] == player for i in range(3)) for j in range(3)) or \
           all(grid[i][i] == player for i in range(3)) or \
           all(grid[i][2 - i] == player for i in range(3))
← Back to All Questions