LeetCode 1212 - Team Scores in Football Tournament

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to compute the total points for each football team after a series of matches in a tournament. The scoring rules are standard: a win gives 3 points, a draw gives 1 point, and a loss gives 0 points.

The input consists of two tables: Teams and Matches. The Teams table contains the unique identifiers and names of all teams. The Matches table lists all the matches that have been played, including the IDs of the host and guest teams and the number of goals each team scored.

The output should list each team's ID, name, and total points accumulated across all matches. The results must be ordered by the number of points in decreasing order, and if two teams have the same points, the team with the smaller team_id comes first.

Key edge cases include teams that never played a match (they should have 0 points), matches where the host and guest scores are equal (draws), and ties in points requiring secondary sorting by team_id. The input guarantees valid team IDs and non-negative integer goals, which simplifies validation.

Approaches

The brute-force approach would involve iterating through each match and updating the points of both the host and guest teams in a temporary data structure like a dictionary or hash map. After processing all matches, we would join this data with the Teams table to get the team names, and finally, we would sort the results. This approach works correctly but can be cumbersome if not implemented using SQL aggregation functions effectively.

The optimal solution leverages SQL's UNION ALL and CASE expressions. The key insight is to treat each match as two separate contributions: one for the host team and one for the guest team. We calculate the points for each side using CASE statements, combine the results using UNION ALL, and then aggregate points by team. Joining this aggregation with the Teams table produces the final output.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(M)	O(T)	Iterate each match and update points in a map, join with Teams
Optimal	O(M + T log T)	O(T)	Use SQL aggregation with `CASE` and `UNION ALL`, order by points

Here, M is the number of matches and T is the number of teams.

Algorithm Walkthrough

For each match, determine the points for the host team: 3 points if the host scored more than the guest, 1 point if tied, 0 otherwise.
Similarly, determine the points for the guest team: 3 points if the guest scored more than the host, 1 point if tied, 0 otherwise.
Create a unified dataset using UNION ALL where each row represents a team and points from a single match. This effectively flattens all matches into a list of points per team.
Aggregate the points by team_id using SUM. This provides the total points per team.
Join the aggregated points with the Teams table to include team names.
Order the results by total points in descending order, and for ties, sort by team_id in ascending order.

Why it works: By treating each team separately for each match and summing their points, we capture all possible outcomes correctly. The join with Teams ensures that teams with zero points are included, and ordering satisfies the output requirement.

Python Solution

# Python solution using SQL syntax via sqlite3 or similar
import sqlite3
from typing import List, Tuple

def team_scores(conn: sqlite3.Connection) -> List[Tuple[int, str, int]]:
    query = """
    WITH points AS (
        SELECT host_team AS team_id,
               CASE
                   WHEN host_goals > guest_goals THEN 3
                   WHEN host_goals = guest_goals THEN 1
                   ELSE 0
               END AS point
        FROM Matches
        UNION ALL
        SELECT guest_team AS team_id,
               CASE
                   WHEN guest_goals > host_goals THEN 3
                   WHEN guest_goals = host_goals THEN 1
                   ELSE 0
               END AS point
        FROM Matches
    )
    SELECT t.team_id, t.team_name, COALESCE(SUM(p.point), 0) AS num_points
    FROM Teams t
    LEFT JOIN points p ON t.team_id = p.team_id
    GROUP BY t.team_id, t.team_name
    ORDER BY num_points DESC, t.team_id ASC;
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

In this implementation, we first calculate the points for each team per match using a CASE statement and combine host and guest contributions using UNION ALL. The COALESCE ensures that teams with no matches get 0 points. The final aggregation and ordering produce the desired result.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "log"
)

type TeamScore struct {
    TeamID    int
    TeamName  string
    NumPoints int
}

func TeamScores(db *sql.DB) ([]TeamScore, error) {
    query := `
    WITH points AS (
        SELECT host_team AS team_id,
               CASE
                   WHEN host_goals > guest_goals THEN 3
                   WHEN host_goals = guest_goals THEN 1
                   ELSE 0
               END AS point
        FROM Matches
        UNION ALL
        SELECT guest_team AS team_id,
               CASE
                   WHEN guest_goals > host_goals THEN 3
                   WHEN guest_goals = host_goals THEN 1
                   ELSE 0
               END AS point
        FROM Matches
    )
    SELECT t.team_id, t.team_name, COALESCE(SUM(p.point), 0) AS num_points
    FROM Teams t
    LEFT JOIN points p ON t.team_id = p.team_id
    GROUP BY t.team_id, t.team_name
    ORDER BY num_points DESC, t.team_id ASC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []TeamScore
    for rows.Next() {
        var ts TeamScore
        if err := rows.Scan(&ts.TeamID, &ts.TeamName, &ts.NumPoints); err != nil {
            return nil, err
        }
        results = append(results, ts)
    }
    return results, nil
}

In Go, the logic mirrors Python but uses sql.DB and rows.Scan to retrieve results. COALESCE handles teams with no matches.

Worked Examples

Using Example 1, the matches produce the following points per match:

Match ID	Host Points	Guest Points
1	3	0
2	1	1
3	3	0
4	0	3
5	0	3

Aggregating by team:

Team ID	Total Points
10	7
20	3
30	1
40	0
50	3

Joining with team names and ordering by points and ID gives the final result as shown in the problem statement.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(M + T log T)	Calculating points is O(M), aggregating is O(M), sorting T teams is O(T log T)
Space	O(T)	Store points per team for aggregation

The time complexity is dominated by sorting the teams, while space complexity is for storing intermediate points.

Test Cases

# test cases using assert

# example case
assert team_scores(conn := sqlite3.connect(":memory:")) == [
    (10, "Leetcode FC", 7),
    (20, "NewYork FC", 3),
    (50, "Toronto FC", 3),
    (30, "Atlanta FC", 1),
    (40, "Chicago FC", 0)
]  # tests normal scenario with multiple matches

# edge case: team with no matches
# team 60 exists but has no matches
assert team_scores(conn := sqlite3.connect(":memory:")) == [
    (60, "Empty FC", 0)
]

# edge case: all draws
# every match results in a draw
# points should be equal across all teams
# ...

# edge case: all wins for single team
# points distribution should reflect single dominant team
# ...

Test	Why
normal scenario	Validates aggregation and ordering logic
team with no matches	Ensures 0 points are correctly handled
all draws	Checks correct assignment of 1 point per draw
all wins for one team	Ensures aggregation handles dominant scoring correctly

Edge Cases

One edge case is teams that never participate in any match. If we do not handle this correctly using a LEFT JOIN and COALESCE, these teams could be omitted or show null points.

Another edge case is matches that end in a draw. Naively giving 3 points to one team or ignoring draws would produce incorrect results. Using CASE ensures both teams get