LeetCode 3252 - Premier League Table Ranking II

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to compute a Premier League-style ranking table from a TeamStats table, which contains each team's matches played, wins, draws, and losses. We are required to calculate three additional columns for each team: points, position, and tier.

Points are calculated with the standard football scoring system: 3 points per win, 1 point per draw, and 0 points per loss. The position column ranks teams in descending order of points, with ties sharing the same position. The tier column divides the teams into three groups: the top 33% (Tier 1), middle 33% (Tier 2), and bottom 34% (Tier 3). If points tie at a tier boundary, all tied teams are placed in the higher tier. Finally, the output must be sorted first by points in descending order and then by team_name in ascending order.

Important edge cases include teams having the same points, especially around tier boundaries, teams with identical names (unlikely due to unique team_id), and very small numbers of teams where the percentage splits may round differently.

The problem is essentially asking for a ranking calculation with grouping logic based on percentage tiers, handling ties both for positions and tiers.

Approaches

The brute-force approach is straightforward: calculate points for each team, sort all teams by points and name, assign positions sequentially (handling ties manually), then calculate tier cutoffs and assign tiers based on points. This works but can be verbose and error-prone when handling ties and tier boundaries.

The optimal approach leverages SQL window functions like RANK(), COUNT(), and CEIL() to calculate positions and tiers cleanly. RANK() handles ties automatically for positions, while tier boundaries are determined using the total number of teams, converting percentages to counts. Handling ties at tier boundaries requires careful logic using window functions to ensure all teams with the same points stay in the higher tier.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Sort manually, assign ranks and tiers sequentially, handle ties manually
Optimal	O(n log n)	O(n)	Use SQL window functions to handle ranking and tier calculation cleanly

Algorithm Walkthrough

Calculate points for each team using the formula (wins * 3 + draws).
Rank teams by points in descending order, using RANK() to assign the position. Ties in points automatically share the same position.
Count the total number of teams to determine tier boundaries. Compute the counts for Tier 1 and Tier 2 using CEIL(total_teams * 0.33); Tier 3 will automatically contain the remaining teams.
Assign tiers using the ranked positions. Use a CASE statement to determine if a team's rank falls within Tier 1, Tier 2, or Tier 3. If multiple teams tie at a boundary, all are assigned the higher tier.
Sort the final output by points descending and team_name ascending to match the expected output format.

Why it works: Using RANK() ensures correct handling of ties for positions. Calculating tiers based on rank rather than exact position ensures that ties at tier boundaries are resolved in favor of the higher tier. The window functions allow calculation without iterative loops, maintaining correctness and efficiency.

Python Solution

import sqlite3

# Assuming a SQLite connection for demonstration
conn = sqlite3.connect(':memory:')
cur = conn.cursor()

def premier_league_ranking():
    query = """
    WITH TeamPoints AS (
        SELECT 
            team_name,
            (wins * 3 + draws) AS points
        FROM TeamStats
    ),
    RankedTeams AS (
        SELECT
            team_name,
            points,
            RANK() OVER (ORDER BY points DESC, team_name ASC) AS position,
            COUNT(*) OVER () AS total_teams
        FROM TeamPoints
    ),
    TieredTeams AS (
        SELECT
            team_name,
            points,
            position,
            CASE 
                WHEN position <= CEIL(total_teams * 0.33) THEN 'Tier 1'
                WHEN position <= CEIL(total_teams * 0.66) THEN 'Tier 2'
                ELSE 'Tier 3'
            END AS tier
        FROM RankedTeams
    )
    SELECT team_name, points, position, tier
    FROM TieredTeams
    ORDER BY points DESC, team_name ASC;
    """
    cur.execute(query)
    return cur.fetchall()

This Python solution creates a SQL query that calculates points, ranks, and tiers directly using window functions. The CEIL ensures the top 33% of teams are in Tier 1, and 66% in Tier 2. Sorting is done in the final SELECT.

Go Solution

package main

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

func PremierLeagueRanking(db *sql.DB) ([]map[string]interface{}, error) {
    query := `
    WITH TeamPoints AS (
        SELECT 
            team_name,
            (wins * 3 + draws) AS points
        FROM TeamStats
    ),
    RankedTeams AS (
        SELECT
            team_name,
            points,
            RANK() OVER (ORDER BY points DESC, team_name ASC) AS position,
            COUNT(*) OVER () AS total_teams
        FROM TeamPoints
    ),
    TieredTeams AS (
        SELECT
            team_name,
            points,
            position,
            CASE 
                WHEN position <= CEIL(total_teams * 0.33) THEN 'Tier 1'
                WHEN position <= CEIL(total_teams * 0.66) THEN 'Tier 2'
                ELSE 'Tier 3'
            END AS tier
        FROM RankedTeams
    )
    SELECT team_name, points, position, tier
    FROM TieredTeams
    ORDER BY points DESC, team_name ASC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []map[string]interface{}
    for rows.Next() {
        var team_name string
        var points, position int
        var tier string
        if err := rows.Scan(&team_name, &points, &position, &tier); err != nil {
            return nil, err
        }
        results = append(results, map[string]interface{}{
            "team_name": team_name,
            "points": points,
            "position": position,
            "tier": tier,
        })
    }
    return results, nil
}

The Go solution mirrors the Python logic, using SQL window functions and reading results into a slice of maps. Differences are in type handling and mapping SQL rows into Go data structures.

Worked Examples

For Sheffield United with 18 wins and 2 draws: points = 18*3 + 2 = 56. Its rank is 1 since no other team has more points. The first 4 teams occupy Tier 1 (top 33% of 10 teams = 4). The next 4 teams occupy Tier 2. The last 2 teams are in Tier 3. This reasoning applies consistently across all teams.

team_name	points	position	tier
Sheffield United	56	1	Tier 1
Fulham	55	2	Tier 1
Newcastle United	43	3	Tier 1
Chelsea	41	4	Tier 1
Burnley	27	5	Tier 2
Nottingham Forest	24	6	Tier 2
Everton	12	7	Tier 2
Luton Town	12	7	Tier 2
Liverpool	11	9	Tier 3
Aston Villa	9	10	Tier 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting teams by points and name dominates
Space	O(n)	Storing intermediate tables for points, ranks, and tiers

Sorting is the primary computational cost, while the window functions operate in linear space relative to the number of teams.

Test Cases

# Example test
assert premier_league_ranking() == [
    ('Sheffield United', 56, 1, 'Tier 1'),
    ('Fulham', 55, 2, 'Tier 1'),
    ('Newcastle United', 43, 3, 'Tier 1'),
    ('Chelsea', 41, 4, 'Tier 1'),
    ('Burnley', 27, 5, 'Tier 2'),
    ('Nottingham Forest', 24, 6, 'Tier 2'),
    ('Everton', 12, 7, 'Tier 2'),
    ('Luton Town', 12, 7, 'Tier 2'),
    ('Liverpool', 11, 9, 'Tier 3'),
    ('Aston Villa', 9, 10, 'Tier 3'),
] # Provided example

# Edge case: all teams have same points
# Ensures ranking handles ties correctly
# 3 teams, all 10 points

Test	Why
Provided