Leetcode – Find Winner on a Tic Tac Toe Game Solution

Spread the love

Tic-Tac-Toe is a classic board game that involves strategy, tactics, and observation. When given a set of Tic-Tac-Toe board states, you might want to determine who the winner is, or if the game is a draw or still ongoing. This can be done programmatically, and the Leetcode problem titled “Find Winner on a Tic-Tac-Toe Game” asks you to do just that. In this comprehensive guide, we will explore multiple ways to tackle this problem using Python.

Table of Contents

  1. Problem Description
  2. Approach 1: Brute-Force Method
  3. Approach 2: Optimized Algorithm
  4. Time and Space Complexity Analysis
  5. Conclusion

1. Problem Description

The problem essentially provides you with a list of moves made by players ‘A’ and ‘B’ during a Tic-Tac-Toe game. Your task is to determine the winner or the state of the game based on these moves.

Problem Constraints

  • The board is 3×3 in dimension.
  • Players take turns.
  • There will be a winner as soon as one of the players has three of their marks in a horizontal, vertical, or diagonal row.

2. Approach 1: Brute-Force Method

Algorithm

  1. Initialize a 3×3 board represented by a list of lists.
  2. Iterate through the given moves and populate the board.
  3. Check each row, column, and diagonal to determine the winner.

Python Code

def tictactoe(moves):
    board = [[' ' for _ in range(3)] for _ in range(3)]
    
    # Populate board
    for i, (x, y) in enumerate(moves):
        player = 'A' if i % 2 == 0 else 'B'
        board[x][y] = player
    
    # Check rows and columns
    for i in range(3):
        if board[i][0] == board[i][1] == board[i][2] != ' ':
            return board[i][0]
        if board[0][i] == board[1][i] == board[2][i] != ' ':
            return board[0][i]
    
    # Check diagonals
    if board[0][0] == board[1][1] == board[2][2] != ' ':
        return board[0][0]
    if board[0][2] == board[1][1] == board[2][0] != ' ':
        return board[0][2]
    
    # Check if it's a draw or pending
    return "Draw" if len(moves) == 9 else "Pending"

print(tictactoe([[0,0],[2,0],[1,1],[2,1],[2,2]]))  # Output should be 'A'

3. Approach 2: Optimized Algorithm

Algorithm

  1. Use two sets to keep track of moves made by ‘A’ and ‘B’.
  2. Use a list of all possible winning combinations.
  3. Iterate through the moves, and after each move, check if any winning combination exists in the set.

Python Code

def tictactoe(moves):
    A_moves = set()
    B_moves = set()
    
    for i, (x, y) in enumerate(moves):
        if i % 2 == 0:
            A_moves.add((x, y))
        else:
            B_moves.add((x, y))
    
    winning_positions = [
        {(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 positions in winning_positions:
        if positions.issubset(A_moves):
            return 'A'
        if positions.issubset(B_moves):
            return 'B'
    
    return "Draw" if len(moves) == 9 else "Pending"

print(tictactoe([[0,0],[2,0],[1,1],[2,1],[2,2]]))  # Output should be 'A'

4. Time and Space Complexity Analysis

Both the brute-force and optimized approaches have a time complexity of O(1) as the board size and the number of winning positions are constant. The space complexity is also O(1).

5. Conclusion

We’ve gone through two approaches to solve the “Find Winner on a Tic-Tac-Toe Game” problem on LeetCode using Python. The first method uses brute force to populate the board and then scan it, while the second, optimized approach uses sets and predefined winning positions. Both methods have their merits, and understanding both can help deepen your grasp of problem-solving techniques in Python.

Leave a Reply