LeetCode 2175 - The Change in Global Rankings

This problem asks us to determine how the global rankings of national teams change after their points are updated. We are given two database tables: The TeamPoints table contains the current ranking information for each team.

leetcodemediumdatabase

LeetCode Problem 2175

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to determine how the global rankings of national teams change after their points are updated.

We are given two database tables:

The TeamPoints table contains the current ranking information for each team. Every row includes:

  • team_id, the unique identifier for the team
  • name, the country name
  • points, the current ranking points

The PointsChange table contains the point adjustment for every team. Each row includes:

  • team_id
  • points_change, which may be positive, negative, or zero

The ranking system works as follows:

  1. Teams are sorted by points in descending order.
  2. If two teams have the same number of points, they are ordered lexicographically by their country name.

The task is to:

  1. Compute the original rankings.
  2. Apply the point changes.
  3. Compute the updated rankings.
  4. Return the difference between the old rank and the new rank for every team.

The output column rank_diff represents:

old_rank - new_rank

This means:

  • A positive value means the team improved its ranking.
  • A negative value means the team dropped in ranking.
  • Zero means the ranking stayed the same.

The problem guarantees that:

  • Every team_id is unique in both tables.
  • Every team appearing in TeamPoints also appears in PointsChange.

This guarantee is important because it means we never need to handle missing updates or duplicate teams.

An important detail is the tie-breaking rule. Two teams with equal points are ranked using lexicographical ordering of their names. A naive implementation that ignores this secondary ordering will produce incorrect ranks.

Another important edge case occurs when multiple teams gain or lose enough points to completely reorder the rankings. The solution must recompute rankings from scratch after the updates rather than attempting incremental adjustments.

Approaches

Brute Force Approach

The brute-force solution computes rankings manually by comparing every team against every other team.

First, we calculate the original rank for each team. For every team, we compare it against all other teams and count how many teams should appear before it according to the ranking rules. The rank becomes:

1 + number of teams ahead of it

After that, we update all points using the points_change values and repeat the same pairwise comparison process to compute the new rankings.

Finally, we subtract the new rank from the old rank for each team.

This approach is correct because it directly implements the ranking definition. However, it is inefficient because ranking computation requires comparing every pair of teams, resulting in quadratic complexity.

Optimal Approach

The key observation is that rankings are entirely determined by sorting order.

Instead of comparing every team against every other team, we can:

  1. Sort teams by their original ranking criteria.
  2. Assign ranks based on sorted order.
  3. Update points.
  4. Sort again using updated points.
  5. Assign new ranks.
  6. Compute the difference.

Sorting automatically handles both the primary ordering by points and the secondary ordering by team name.

This is significantly more efficient because sorting takes O(n log n) time instead of O(n²).

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Compares every team with every other team twice
Optimal O(n log n) O(n) Uses sorting to compute rankings efficiently

Algorithm Walkthrough

  1. Join the two tables using team_id.

We first combine the original points and point changes so each team record contains:

  • team ID
  • team name
  • original points
  • updated points

The updated points are computed as:

updated_points = points + points_change
  1. Compute the original rankings.

We sort all teams using:

  • descending original points
  • ascending lexicographical name

After sorting, the first team gets rank 1, the second gets rank 2, and so on.

We store these ranks in a mapping from team_id to old_rank. 3. Compute the updated rankings.

We sort the same teams again, but this time using:

  • descending updated points
  • ascending lexicographical name

We assign ranks again and store them as new_rank. 4. Compute rank differences.

For every team:

rank_diff = old_rank - new_rank

A positive result means the team moved up in ranking. 5. Return the final result.

The output contains:

  • team_id
  • name
  • rank_diff

Why it works

The algorithm works because ranking is completely determined by the sorted order of teams. By sorting according to the exact ranking rules both before and after updating points, we reproduce the official rankings precisely. Since every team receives exactly one position in each sorted list, subtracting the positions correctly measures ranking movement.

Python Solution

import pandas as pd

def global_ratings_change(
    team_points: pd.DataFrame,
    points_change: pd.DataFrame
) -> pd.DataFrame:
    
    # Merge both tables
    teams = team_points.merge(points_change, on="team_id")
    
    # Compute updated points
    teams["new_points"] = teams["points"] + teams["points_change"]
    
    # Original rankings
    original = teams.sort_values(
        by=["points", "name"],
        ascending=[False, True]
    ).reset_index(drop=True)
    
    original["old_rank"] = range(1, len(original) + 1)
    
    # Updated rankings
    updated = teams.sort_values(
        by=["new_points", "name"],
        ascending=[False, True]
    ).reset_index(drop=True)
    
    updated["new_rank"] = range(1, len(updated) + 1)
    
    # Build rank mappings
    old_rank_map = original.set_index("team_id")["old_rank"]
    new_rank_map = updated.set_index("team_id")["new_rank"]
    
    # Compute final result
    result = teams[["team_id", "name"]].copy()
    
    result["rank_diff"] = (
        old_rank_map[result["team_id"]].values
        - new_rank_map[result["team_id"]].values
    )
    
    return result

The implementation begins by merging the two input tables using team_id. This gives access to both the original points and the corresponding point changes for every team.

Next, the code computes the updated score for each team by adding points_change to the original points.

The algorithm then creates two sorted versions of the data. The first sorting computes the original rankings, while the second sorting computes rankings after updates. Both sorts use the exact ranking rules required by the problem:

  • descending points
  • ascending lexicographical name

After sorting, ranks are assigned sequentially using range(1, n + 1).

The code stores these rankings in lookup mappings indexed by team_id. This allows fast retrieval of both old and new ranks for each team.

Finally, the result dataframe is constructed and the rank difference is calculated as:

old_rank - new_rank

This directly matches the definition required by the problem.

Go Solution

package main

import (
	"sort"
)

type TeamPoints struct {
	TeamID int
	Name   string
	Points int
}

type PointsChange struct {
	TeamID      int
	PointsChange int
}

type Result struct {
	TeamID  int
	Name    string
	RankDiff int
}

type Team struct {
	TeamID    int
	Name      string
	Points    int
	NewPoints int
}

func globalRatingsChange(
	teamPoints []TeamPoints,
	pointsChange []PointsChange,
) []Result {

	changeMap := make(map[int]int)

	for _, p := range pointsChange {
		changeMap[p.TeamID] = p.PointsChange
	}

	teams := make([]Team, 0)

	for _, t := range teamPoints {
		teams = append(teams, Team{
			TeamID:    t.TeamID,
			Name:      t.Name,
			Points:    t.Points,
			NewPoints: t.Points + changeMap[t.TeamID],
		})
	}

	oldOrder := make([]Team, len(teams))
	copy(oldOrder, teams)

	sort.Slice(oldOrder, func(i, j int) bool {
		if oldOrder[i].Points == oldOrder[j].Points {
			return oldOrder[i].Name < oldOrder[j].Name
		}
		return oldOrder[i].Points > oldOrder[j].Points
	})

	oldRank := make(map[int]int)

	for i, team := range oldOrder {
		oldRank[team.TeamID] = i + 1
	}

	newOrder := make([]Team, len(teams))
	copy(newOrder, teams)

	sort.Slice(newOrder, func(i, j int) bool {
		if newOrder[i].NewPoints == newOrder[j].NewPoints {
			return newOrder[i].Name < newOrder[j].Name
		}
		return newOrder[i].NewPoints > newOrder[j].NewPoints
	})

	newRank := make(map[int]int)

	for i, team := range newOrder {
		newRank[team.TeamID] = i + 1
	}

	result := make([]Result, 0)

	for _, team := range teams {
		result = append(result, Result{
			TeamID:  team.TeamID,
			Name:    team.Name,
			RankDiff: oldRank[team.TeamID] - newRank[team.TeamID],
		})
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

A map is used to associate each team_id with its point change. This allows constant-time lookup while constructing updated team records.

Go does not provide built-in dataframe operations, so slices and custom structs are used instead. The sorting logic is implemented using sort.Slice with custom comparison functions.

Two separate copies of the team slice are created so the original and updated rankings can be sorted independently.

Since Go slices are references to shared backing arrays, using copy() is important to avoid modifying the same slice twice unintentionally.

Go integers safely handle the constraints for this problem, so no special overflow handling is necessary.

Worked Examples

Example 1

Initial tables:

team_id name points
3 Algeria 1431
1 Senegal 2132
2 New Zealand 1402
4 Croatia 1817
team_id points_change
3 399
2 0
4 13
1 -22

Step 1, Compute Updated Points

team_id name original change updated
3 Algeria 1431 399 1830
1 Senegal 2132 -22 2110
2 New Zealand 1402 0 1402
4 Croatia 1817 13 1830

Step 2, Original Rankings

Sort by descending points:

Rank Team Points
1 Senegal 2132
2 Croatia 1817
3 Algeria 1431
4 New Zealand 1402

Old rank map:

1 -> 1
4 -> 2
3 -> 3
2 -> 4

Step 3, Updated Rankings

Updated points:

Team Updated Points
Senegal 2110
Algeria 1830
Croatia 1830
New Zealand 1402

Algeria and Croatia tie at 1830 points.

Lexicographical order decides the tie:

Algeria < Croatia

Final rankings:

Rank Team Points
1 Senegal 2110
2 Algeria 1830
3 Croatia 1830
4 New Zealand 1402

New rank map:

1 -> 1
3 -> 2
4 -> 3
2 -> 4

Step 4, Compute Differences

Team Old Rank New Rank Rank Diff
Senegal 1 1 0
Croatia 2 3 -1
Algeria 3 2 1
New Zealand 4 4 0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Dominated by sorting the teams twice
Space O(n) Stores ranking mappings and sorted copies

The most expensive operations are the two sorting passes. Each sort requires O(n log n) time. All remaining operations, including merging, rank assignment, and difference computation, are linear.

The auxiliary space usage comes from storing intermediate sorted structures and rank lookup maps.

Test Cases

import pandas as pd

# Example case
team_points = pd.DataFrame({
    "team_id": [3, 1, 2, 4],
    "name": ["Algeria", "Senegal", "New Zealand", "Croatia"],
    "points": [1431, 2132, 1402, 1817]
})

points_change = pd.DataFrame({
    "team_id": [3, 2, 4, 1],
    "points_change": [399, 0, 13, -22]
})

result = global_ratings_change(team_points, points_change)

assert set(result["rank_diff"]) == {0, -1, 1}  # provided example

# Single team
team_points = pd.DataFrame({
    "team_id": [1],
    "name": ["Brazil"],
    "points": [2000]
})

points_change = pd.DataFrame({
    "team_id": [1],
    "points_change": [100]
})

result = global_ratings_change(team_points, points_change)

assert result.iloc[0]["rank_diff"] == 0  # only one team

# Tie after update
team_points = pd.DataFrame({
    "team_id": [1, 2],
    "name": ["Argentina", "Brazil"],
    "points": [1000, 900]
})

points_change = pd.DataFrame({
    "team_id": [1, -100],
    "points_change": [0, 100]
})

result = global_ratings_change(team_points, points_change)

assert sorted(result["rank_diff"].tolist()) == [-1, 1]  # rankings swap

# No ranking changes
team_points = pd.DataFrame({
    "team_id": [1, 2, 3],
    "name": ["A", "B", "C"],
    "points": [300, 200, 100]
})

points_change = pd.DataFrame({
    "team_id": [1, 2, 3],
    "points_change": [10, 10, 10]
})

result = global_ratings_change(team_points, points_change)

assert all(result["rank_diff"] == 0)  # same ordering

# Lexicographical tie handling
team_points = pd.DataFrame({
    "team_id": [1, 2],
    "name": ["Algeria", "Croatia"],
    "points": [1000, 1000]
})

points_change = pd.DataFrame({
    "team_id": [1, 2],
    "points_change": [0, 0]
})

result = global_ratings_change(team_points, points_change)

assert all(result["rank_diff"] == 0)  # stable lexicographic order
Test Why
Provided example Verifies standard ranking updates
Single team Tests minimum input size
Tie after update Ensures ranking swaps are handled
No ranking changes Verifies stable rankings
Lexicographical tie handling Confirms tie-breaking correctness

Edge Cases

Teams Become Tied After Updates

One important edge case occurs when two or more teams end up with identical scores after the point changes are applied. A buggy implementation might preserve the old ordering or use arbitrary ordering instead of lexicographical sorting.

This implementation explicitly sorts by:

(points descending, name ascending)

both before and after updates, ensuring ties are handled correctly every time.

Negative Point Changes

Some teams may lose points instead of gaining them. A naive solution might assume rankings only improve after updates.

The algorithm recomputes the entire ranking from scratch after updates, so decreases in ranking are handled naturally. Negative rank_diff values correctly represent teams moving downward.

Single Team Input

If only one team exists, both the old and new rankings must remain 1.

Some implementations accidentally introduce off-by-one errors when assigning ranks. Since this solution always assigns ranks using:

range(1, n + 1)

the single-team case works correctly and produces a rank difference of 0.

Large Reordering of Rankings

A team could gain enough points to jump from the bottom to the top of the rankings. Incremental update strategies are often error-prone in such situations.

This solution avoids that issue entirely by sorting the full dataset again after applying updates. The recomputed ranking is always globally correct regardless of how dramatically the ordering changes.