LeetCode 1194 - Tournament Winners

The problem asks us to determine the winner in each group of players based on their accumulated points across multiple matches. We are given two tables: Players and Matches.

leetcodeharddatabase

LeetCode Problem 1194

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem asks us to determine the winner in each group of players based on their accumulated points across multiple matches. We are given two tables: Players and Matches. The Players table maps each player to a group, while the Matches table records each match's score between two players, where all matches occur within the same group.

The winner of a group is the player with the highest total points within that group. In case of a tie, the player with the smallest player_id wins. The output is a table showing the winning player_id for each group_id.

Important constraints and observations include that every player belongs to exactly one group, each match is between players of the same group, and ties are resolved deterministically using player_id. Edge cases include players with zero matches, multiple players tying in score, or groups with a single player.

Approaches

The brute-force approach would involve iterating through every player in every group, summing all their scores from the Matches table, and then determining the maximum manually for each group. This is correct but inefficient because it requires repeated full-table scans for each player, resulting in high computational cost.

A more optimal approach leverages SQL aggregation. We can compute total points per player using SUM on scores from the Matches table, then join with the Players table to get their group. Using a window function such as ROW_NUMBER() partitioned by group_id and ordered by total points descending, and player_id ascending, we can efficiently select the top player for each group. This approach avoids repeated scanning and leverages SQL’s built-in optimization for aggregation and sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(P * M) O(P) Sum scores per player by scanning the Matches table multiple times, inefficient for large tables
Optimal O(M + P) O(P) Aggregate scores per player once, rank within groups, select top player

Algorithm Walkthrough

  1. First, compute the total points scored by each player across all matches. This is done by summing the first_score and second_score for each player depending on whether they were the first or second player in the match.
  2. Next, join this total points table with the Players table to associate each player's total points with their group_id.
  3. Use a window function such as ROW_NUMBER() partitioned by group_id and ordered by total points descending and player_id ascending. This will assign rank 1 to the player with the most points in the group, breaking ties with the lowest player_id.
  4. Finally, select only the players with rank 1 from each group. This gives the winner per group according to the rules.

Why it works: By aggregating each player's points first, we ensure correctness of the total score computation. The window function guarantees that ties are resolved properly by the player_id. Selecting only rank 1 ensures only one winner per group.

Python Solution

import pandas as pd

def tournament_winners(players: pd.DataFrame, matches: pd.DataFrame) -> pd.DataFrame:
    # Compute total points for each player
    first_points = matches[['first_player', 'first_score']].rename(columns={'first_player': 'player_id', 'first_score': 'points'})
    second_points = matches[['second_player', 'second_score']].rename(columns={'second_player': 'player_id', 'second_score': 'points'})
    all_points = pd.concat([first_points, second_points])
    
    total_points = all_points.groupby('player_id', as_index=False)['points'].sum()
    
    # Merge with Players table to get group_id
    player_groups = players.merge(total_points, on='player_id', how='left').fillna(0)
    
    # Sort by group_id, points descending, player_id ascending
    player_groups.sort_values(by=['group_id', 'points', 'player_id'], ascending=[True, False, True], inplace=True)
    
    # Keep the top player per group
    winners = player_groups.groupby('group_id').first().reset_index()[['group_id', 'player_id']]
    
    return winners

The code first separates scores for first and second players, concatenates them, and aggregates points per player. After merging with the Players table to get the group, it sorts by group and ranking criteria and selects the top player per group.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/go-sql-driver/mysql"
    "fmt"
)

func TournamentWinners(db *sql.DB) ([][2]int, error) {
    query := `
        WITH player_points AS (
            SELECT player_id, SUM(points) as total_points, group_id
            FROM (
                SELECT first_player as player_id, first_score as points, p.group_id
                FROM Matches m
                JOIN Players p ON m.first_player = p.player_id
                UNION ALL
                SELECT second_player, second_score, p.group_id
                FROM Matches m
                JOIN Players p ON m.second_player = p.player_id
            ) AS combined
            GROUP BY player_id, group_id
        ),
        ranked AS (
            SELECT group_id, player_id,
                   ROW_NUMBER() OVER (PARTITION BY group_id ORDER BY total_points DESC, player_id ASC) AS rn
            FROM player_points
        )
        SELECT group_id, player_id
        FROM ranked
        WHERE rn = 1;
    `

    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results [][2]int
    for rows.Next() {
        var groupID, playerID int
        if err := rows.Scan(&groupID, &playerID); err != nil {
            return nil, err
        }
        results = append(results, [2]int{groupID, playerID})
    }
    return results, nil
}

The Go version leverages SQL CTEs to compute points and ranks. It then scans the results into a slice of arrays. Go-specific differences include handling SQL query results explicitly with rows.Scan and managing resource cleanup with defer rows.Close().

Worked Examples

Example 1:

After computing total points:

player_id group_id total_points
15 1 3
25 1 2
30 1 3
45 1 0
10 2 0
35 2 1
50 2 1
20 3 2
40 3 5

After ranking within groups:

group_id player_id total_points rank
1 15 3 1
2 35 1 1
3 40 5 1

Selecting rank 1 players gives the correct winners.

Complexity Analysis

Measure Complexity Explanation
Time O(M + P log P) M for scanning matches to sum points, P log P for sorting players by group
Space O(P) Storage of aggregated points per player

The time complexity is dominated by aggregation and sorting. Space complexity is linear in the number of players since we store total points and group associations.

Test Cases

# Example from problem statement
players_df = pd.DataFrame({
    'player_id': [15,25,30,45,10,35,50,20,40],
    'group_id': [1,1,1,1,2,2,2,3,3]
})
matches_df = pd.DataFrame({
    'match_id': [1,2,3,4,5],
    'first_player': [15,30,30,40,35],
    'second_player': [45,25,15,20,50],
    'first_score': [3,1,2,5,1],
    'second_score': [0,2,0,2,1]
})
result = tournament_winners(players_df, matches_df)
assert set(map(tuple, result.to_numpy())) == {(1,15),(2,35),(3,40)}  # Basic example

# Edge case: player with no matches
players_df2 = pd.DataFrame({'player_id':[1,2],'group_id':[1,1]})
matches_df2 = pd.DataFrame(columns=['match_id','first_player','second_player','first_score','second_score'])
result2 = tournament_winners(players_df2, matches_df2)
assert set(map(tuple, result2.to_numpy())) == {(1,1)}  # player_id 1 wins tie-break by ID

# Tie in points
players_df3 = pd.DataFrame({'player_id':[1,2],'group_id':[1,1]})
matches_df3 = pd.DataFrame({'match_id':[1],'first_player':[1],'second_player':[2],'first_score':[2],'second_score':[2]})
result3 = tournament_winners(players_df3, matches_df3)
assert set(map(tuple, result3.to_numpy())) == {(1,1)}  # tie broken by lowest