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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Winner on a Tic Tac Toe Game

Number: 1400

Difficulty: Easy

Paid? No

Companies: Meta, Amazon, Apple, Google, Tesla, TikTok, Qualcomm, Zoho

Problem Description

Two players (A and B) play Tic Tac Toe on a 3x3 grid. Player A always plays first with 'X' and player B with 'O'. Given an array of moves where each move indicates the cell played, determine the outcome of the game: return "A" or "B" if a player wins, "Draw" if all cells are filled with no winner, or "Pending" if the game is still ongoing.

Key Insights

  • Use board simulation by tracking rows, columns, and both diagonals.
  • Represent moves with a numeric value (e.g., +1 for A, -1 for B) to check winning conditions easily.
  • A win occurs when the absolute value of any row, column, or diagonal sum reaches 3.
  • The moves array directly guides the simulation; each move’s index determines the player.

Space and Time Complexity

Time Complexity: O(1) (since the board size and maximum moves are fixed at 3x3 grid with at most 9 moves)
Space Complexity: O(1) (only constant extra space is used for counters)

Solution

We simulate each move and update counts for the affected row, column, and possibly the two diagonals:

  1. Initialize counters for rows, columns, and the two diagonals.
  2. For each move, determine the current player using the move index (even for A, odd for B). Assign +1 for A and -1 for B.
  3. Update the corresponding row and column counters.
  4. Check if the move is on the main diagonal (row == col) or anti-diagonal (row + col == 2) and update counts accordingly.
  5. After each update, check if the absolute value of any counter equals 3. If so, declare the respective winner.
  6. If all moves are completed without any player winning, return "Draw" if the board is full, or "Pending" otherwise.

Code Solutions

# Python solution for Tic Tac Toe winner detection
def tictactoe(moves):
    # Initialize counters for rows, columns, and diagonals
    rows = [0] * 3
    cols = [0] * 3
    diag = 0
    anti_diag = 0
    
    # Loop through each move with index to determine current player
    for i, (row, col) in enumerate(moves):
        # Player A uses +1, Player B uses -1
        player = 1 if i % 2 == 0 else -1
        
        # Update row and column counters
        rows[row] += player
        cols[col] += player
        
        # Update main diagonal if applicable
        if row == col:
            diag += player
        
        # Update anti-diagonal if applicable
        if row + col == 2:
            anti_diag += player
        
        # Check if any counter reaches a win condition (absolute value equals 3)
        if abs(rows[row]) == 3 or abs(cols[col]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
            return "A" if player == 1 else "B"
    
    # Check if game is ongoing or ended in a draw
    return "Draw" if len(moves) == 9 else "Pending"

# Example usage:
# moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
# print(tictactoe(moves))
← Back to All Questions