LeetCode 3322 - Premier League Table Ranking III

The problem requires calculating a Premier League-style ranking for teams in each season based on their match results.

leetcodemediumdatabase

LeetCode Problem 3322

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem requires calculating a Premier League-style ranking for teams in each season based on their match results. The input is a table SeasonStats that contains the statistics for each team per season, including the number of matches played, wins, draws, losses, goals scored, and goals conceded. Each team is uniquely identified by a combination of season_id and team_id.

We need to compute three derived values for each team: points, goal difference, and position. Points are calculated using the standard football scoring system, where a win gives 3 points, a draw gives 1 point, and a loss gives 0 points. Goal difference is simply goals_for - goals_against. The position of each team within a season is determined first by total points (descending), then by goal difference (descending), and finally alphabetically by team name in ascending order in case of ties.

The expected output is a table with season_id, team_id, team_name, points, goal_difference, and position, ordered by season_id ascending, then by position ascending, and finally by team_name ascending.

Important edge cases include seasons with teams tied on points and goal difference, teams with zero wins or draws, and handling multiple seasons correctly.

Approaches

A brute-force approach would first compute points and goal difference for all teams, then iterate over each season and manually sort the teams by the ranking criteria before assigning positions. While correct, it is cumbersome and inefficient for large datasets, as it requires multiple passes over the data and explicit sorting per season.

The optimal approach leverages SQL window functions. By computing points and goal_difference in a subquery and then using RANK() or DENSE_RANK() partitioned by season_id with an appropriate ORDER BY clause, we can assign the position in a single query efficiently. This approach uses the database engine's internal sorting and ranking mechanisms, which are optimized for such operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) per season O(n) Compute points and goal difference, sort manually for each season
Optimal O(n log n) O(n) Use SQL window functions RANK() or DENSE_RANK() to assign positions efficiently

Algorithm Walkthrough

  1. Compute points for each team using the formula wins * 3 + draws.
  2. Compute goal_difference for each team as goals_for - goals_against.
  3. Use a subquery to calculate these two derived fields along with the original columns.
  4. Apply the RANK() window function partitioned by season_id and ordered by points descending, goal_difference descending, and team_name ascending to determine the position of each team within their season.
  5. Select the final columns: season_id, team_id, team_name, points, goal_difference, and position.
  6. Order the final result by season_id ascending, position ascending, and team_name ascending for deterministic output.

This works because the window function correctly partitions the data by season and computes the rank according to the specified order, ensuring that ties are handled correctly and positions are assigned in accordance with the problem description.

Python Solution

# LeetCode problem requires a SQL solution, but for completeness, here is a Python equivalent
from typing import List, Dict

def premier_league_ranking(stats: List[Dict]) -> List[Dict]:
    for team in stats:
        team['points'] = team['wins'] * 3 + team['draws']
        team['goal_difference'] = team['goals_for'] - team['goals_against']
    
    result = []
    seasons = sorted(set(team['season_id'] for team in stats))
    
    for season in seasons:
        season_teams = [team for team in stats if team['season_id'] == season]
        season_teams.sort(key=lambda x: (-x['points'], -x['goal_difference'], x['team_name']))
        for idx, team in enumerate(season_teams, 1):
            result.append({
                'season_id': team['season_id'],
                'team_id': team['team_id'],
                'team_name': team['team_name'],
                'points': team['points'],
                'goal_difference': team['goal_difference'],
                'position': idx
            })
    
    return result

In this Python implementation, we first augment the original data with points and goal_difference. We then sort the teams for each season by the ranking criteria and enumerate to assign positions. This mirrors the SQL window function approach in a procedural context.

Go Solution

package main

import (
    "sort"
)

type Team struct {
    SeasonID       int
    TeamID         int
    TeamName       string
    MatchesPlayed  int
    Wins           int
    Draws          int
    Losses         int
    GoalsFor       int
    GoalsAgainst   int
    Points         int
    GoalDifference int
    Position       int
}

func PremierLeagueRanking(teams []Team) []Team {
    seasonMap := make(map[int][]*Team)
    
    for i := range teams {
        teams[i].Points = teams[i].Wins*3 + teams[i].Draws
        teams[i].GoalDifference = teams[i].GoalsFor - teams[i].GoalsAgainst
        seasonMap[teams[i].SeasonID] = append(seasonMap[teams[i].SeasonID], &teams[i])
    }
    
    seasons := []int{}
    for season := range seasonMap {
        seasons = append(seasons, season)
    }
    sort.Ints(seasons)
    
    var result []Team
    for _, season := range seasons {
        seasonTeams := seasonMap[season]
        sort.Slice(seasonTeams, func(i, j int) bool {
            if seasonTeams[i].Points != seasonTeams[j].Points {
                return seasonTeams[i].Points > seasonTeams[j].Points
            }
            if seasonTeams[i].GoalDifference != seasonTeams[j].GoalDifference {
                return seasonTeams[i].GoalDifference > seasonTeams[j].GoalDifference
            }
            return seasonTeams[i].TeamName < seasonTeams[j].TeamName
        })
        for pos, team := range seasonTeams {
            team.Position = pos + 1
            result = append(result, *team)
        }
    }
    return result
}

The Go implementation follows the same logic as the Python version but handles sorting with sort.Slice and uses pointers to efficiently update positions within slices.

Worked Examples

Using the provided input for the 2021 season:

team_name wins draws losses goals_for goals_against points goal_difference
Manchester City 29 6 3 99 26 93 73
Liverpool 28 8 2 94 26 92 68
Chelsea 21 11 6 76 33 74 43
Tottenham 22 5 11 69 40 71 29
Arsenal 22 3 13 61 48 69 13

After sorting by points, goal difference, and team name:

position team_name points goal_difference
1 Manchester City 93 73
2 Liverpool 92 68
3 Chelsea 74 43
4 Tottenham 71 29
5 Arsenal 69 13

This matches the expected output.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting all teams within each season dominates the complexity
Space O(n) Storing augmented team data and intermediate season lists

The complexity is primarily determined by sorting the teams for each season. Using SQL window functions delegates this sorting to the database engine.

Test Cases

# Provided example
assert premier_league_ranking([
    {'season_id': 2021, 'team_id': 1, 'team_name': 'Manchester City', 'matches_played': 38, 'wins': 29, 'draws': 6, 'losses': 3, 'goals_for': 99, 'goals_against': 26},
    {'season_id': 2021, 'team_id': 2, 'team_name': 'Liverpool', 'matches_played': 38, 'wins': 28, 'draws': 8, 'losses': 2, 'goals_for': 94, 'goals_against': 26},
    {'season_id': 2021, 'team_id': 3, 'team_name': 'Chelsea', 'matches_played': 38, 'wins': 21, 'draws': 11, 'losses': 6, 'goals_for': 76