Tournament Winners

Problem

Table: Players

+-------------+-------+
| Column Name | Type  |
+-------------+-------+
| player_id   | int   |
| group_id    | int   |
+-------------+-------+
player_id is the primary key (column with unique values) of this table.
Each row of this table indicates the group of each player.

Table: Matches

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| match_id      | int     |
| first_player  | int     |
| second_player | int     |
| first_score   | int     |
| second_score  | int     |
+---------------+---------+
match_id is the primary key (column with unique values) of this table.
Each row is a record of a match, first_player and second_player contain the player_id of each match.
first_score and second_score contain the number of points of the first_player and second_player respectively.
You may assume that, in each match, players belong to the same group.

The winner in each group is the player who scored the maximum total points within the group. In the case of a tie, the lowest player_id wins.

Write a solution to find the winner in each group.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


Input: 
Players table:
+-----------+------------+
| player_id | group_id   |
+-----------+------------+
| 15        | 1          |
| 25        | 1          |
| 30        | 1          |
| 45        | 1          |
| 10        | 2          |
| 35        | 2          |
| 50        | 2          |
| 20        | 3          |
| 40        | 3          |
+-----------+------------+
Matches table:
+------------+--------------+---------------+-------------+--------------+
| match_id   | first_player | second_player | first_score | second_score |
+------------+--------------+---------------+-------------+--------------+
| 1          | 15           | 45            | 3           | 0            |
| 2          | 30           | 25            | 1           | 2            |
| 3          | 30           | 15            | 2           | 0            |
| 4          | 40           | 20            | 5           | 2            |
| 5          | 35           | 50            | 1           | 1            |
+------------+--------------+---------------+-------------+--------------+
Output: 
+-----------+------------+
| group_id  | player_id  |
+-----------+------------+ 
| 1         | 15         |
| 2         | 35         |
| 3         | 40         |
+-----------+------------+

Solution

Method 1 – Aggregate Scores and Find Winners

Intuition

Sum up each player’s total points in all matches, then for each group, select the player with the highest score (lowest player_id in case of tie).

Approach

For each player, sum their total points as first_player and second_player in Matches.
Join with Players to get group_id.
For each group, select the player with the highest total points (lowest player_id in case of tie).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


WITH player_scores AS (
  SELECT player_id,
         SUM(score) AS total_score
    FROM (
      SELECT first_player AS player_id, first_score AS score FROM Matches
      UNION ALL
      SELECT second_player AS player_id, second_score AS score FROM Matches
    ) t
   GROUP BY player_id
)
SELECT p.group_id, p.player_id
FROM Players p
JOIN player_scores s ON p.player_id = s.player_id
WHERE (p.group_id, s.total_score, p.player_id) IN (
  SELECT p2.group_id, MAX(s2.total_score), MIN(p2.player_id)
  FROM Players p2
  JOIN player_scores s2 ON p2.player_id = s2.player_id
  GROUP BY p2.group_id
)
ORDER BY p.group_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


WITH player_scores AS (
  SELECT player_id,
         SUM(score) AS total_score
    FROM (
      SELECT first_player AS player_id, first_score AS score FROM Matches
      UNION ALL
      SELECT second_player AS player_id, second_score AS score FROM Matches
    ) t
   GROUP BY player_id
), ranked AS (
  SELECT p.group_id, p.player_id, s.total_score,
         RANK() OVER (PARTITION BY p.group_id ORDER BY s.total_score DESC, p.player_id ASC) as rnk
  FROM Players p
  JOIN player_scores s ON p.player_id = s.player_id
)
SELECT group_id, player_id
FROM ranked
WHERE rnk = 1
ORDER BY group_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


WITH player_scores AS (
  SELECT player_id,
         SUM(score) AS total_score
    FROM (
      SELECT first_player AS player_id, first_score AS score FROM Matches
      UNION ALL
      SELECT second_player AS player_id, second_score AS score FROM Matches
    )
   GROUP BY player_id
), ranked AS (
  SELECT p.group_id, p.player_id, s.total_score,
         RANK() OVER (PARTITION BY p.group_id ORDER BY s.total_score DESC, p.player_id ASC) as rnk
  FROM Players p
  JOIN player_scores s ON p.player_id = s.player_id
)
SELECT group_id, player_id
FROM ranked
WHERE rnk = 1
ORDER BY group_id;

Complexity

⏰ Time complexity: O(n + m + g log g) where n = players, m = matches, g = groups
🧺 Space complexity: O(n + m)

Problem#

Examples#

Solution#

Method 1 – Aggregate Scores and Find Winners#

Intuition#

Approach#

Code#

Complexity#