Domain 1EasyCORE

Find Winner on a Tic Tac Toe Game

The problem involves determining the winner of a Tic Tac Toe game given a sequence of moves made by two players, A and B. The input is an array `moves` where each element is a pair representing the row and column on the 3x3 grid where a player marks their character ('X' for player A and 'O' for player B). The output should be either "A" if player A wins, "B" if player B wins, "Draw" if all squares are filled without a winner, or "Pending" if there are still moves left to play.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1275. Find Winner on a Tic Tac Toe Game

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 52.8%


Problem Breakdown

The problem involves determining the winner of a Tic Tac Toe game given a sequence of moves made by two players, A and B. The input is an array moves where each element is a pair representing the row and column on the 3x3 grid where a player marks their character (‘X’ for player A and ‘O’ for player B). The output should be either “A” if player A wins, “B” if player B wins, “Draw” if all squares are filled without a winner, or “Pending” if there are still moves left to play.

Inputs:

  • moves: A list of lists where each sublist contains two integers representing the row and column indices on the 3x3 grid.

Outputs:

  • A string indicating the result of the game (“A”, “B”, “Draw”, or “Pending”).

Implicit Constraints/Edge Cases:

  • The input is guaranteed to be valid, meaning it follows the rules of Tic Tac Toe.
  • Player A always starts first and alternates with player B.
  • The grid is initially empty.

Intuition

The brute-force approach would involve simulating the game on a 3x3 grid by iterating through each move and checking for a winner after every move. However, this approach is inefficient in terms of space complexity because it requires maintaining an entire grid state.

A better approach involves keeping track of the number of ‘X’s and ‘O’s placed in each row, column, and diagonal. By doing so, we can determine if any player has achieved a winning condition without needing to store the entire grid. This reduces both time and space complexity.

Approach

  1. Initialize Counters: Create two 3x3 arrays (rows and cols) to keep track of the number of ‘X’s and ‘O’s in each row and column, respectively. Additionally, maintain two variables (diag and anti_diag) to count the number of ‘X’s and ‘O’s on the main diagonal and anti-diagonal.

  2. Simulate Moves: Iterate through the list of moves. For each move:

    • Determine whether it is made by player A or B.
    • Update the corresponding row, column, and diagonal counters based on the move.
    • Check if any counter reaches 3 (indicating a win for the current player).
  3. Determine Result: After processing all moves:

    • If a player has won, return “A” or “B”.
    • If all 9 squares are filled without a winner, return “Draw”.
    • Otherwise, return “Pending”.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of moves. We iterate through each move once.
  • Space Complexity: O(1). We use fixed-size arrays to keep track of counts, which does not depend on the input size.

Solution

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows, cols = [0] * 3, [0] * 3
        diag = anti_diag = 0
        
        player = 'A'
        for r, c in moves:
            if player == 'A':
                rows[r] += 1
                cols[c] += 1
                if r == c:
                    diag += 1
                if r + c == 2:
                    anti_diag += 1
            else:
                rows[r] -= 1
                cols[c] -= 1
                if r == c:
                    diag -= 1
                if r + c == 2:
                    anti_diag -= 1
            
            # Check for a win condition
            if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
                return player
            
            # Switch players
            player = 'B' if player == 'A' else 'A'
        
        # Check for a draw or pending game
        return "Draw" if len(moves) == 9 else "Pending"

Edge Cases Handled

  • Empty Input: The problem guarantees that the input is valid, so an empty input is not possible.
  • All Moves Played Without a Winner: If all 9 moves are played and no player has won, the function returns “Draw”.
  • Game Not Finished: If fewer than 9 moves are played and no player has won, the function returns “Pending”.