Problem Description

You need to design a Leaderboard class that manages player scores and provides functionality to track top performers.

The Leaderboard class must implement three main functions:

1. addScore(playerId, score): This function adds points to a player's current score. If the player doesn't exist on the leaderboard yet, they are added with the given score as their initial score. If they already exist, the score is added to their existing total.

2. top(K): This function returns the sum of scores of the top K players. The top players are those with the highest scores on the leaderboard.

3. reset(playerId): This function removes a player from the leaderboard by resetting their score to 0. The problem guarantees that this function will only be called for players who already exist on the leaderboard.

The leaderboard starts empty when initialized.

The solution uses a hash table to store each player's score for quick lookup and updates, combined with a SortedList data structure to maintain scores in sorted order. This allows efficient retrieval of top K scores. When updating scores, the old score is removed from the sorted list and the new score is added to maintain the correct ordering. The top(K) function simply sums the last K elements of the sorted list (which are the K highest scores), and reset removes both the player's entry from the hash table and their score from the sorted list.

Intuition

When we need to track player scores and frequently query the top K players, we face two main challenges: efficiently updating individual player scores and quickly finding the highest scores.

The first thought might be to use just a hash table mapping playerId to score. This gives us O(1) access to any player's score, making addScore and reset operations fast. However, finding the top K players would require sorting all scores every time we call top(K), which is inefficient.

Alternatively, we could maintain a sorted array of all scores. This would make top(K) very fast - just take the last K elements. But updating scores becomes problematic because we'd need to search for and update the player's entry, which could be O(n).

The key insight is to use both data structures together. The hash table d gives us instant access to any player's current score by their ID. The SortedList maintains all scores in sorted order automatically.

When adding a score, if the player already exists, we need to maintain the sorted order correctly. We can't just add the new points to the existing entry in the sorted list - we need to remove the old score value and insert the new total. For example, if a player has 50 points and gains 30 more, we remove 50 from the sorted list and add 80.

This dual structure approach elegantly handles all operations: addScore uses the hash table to check existence and track totals while maintaining the sorted list, top(K) simply sums the largest K values from the sorted list, and reset removes entries from both structures. The SortedList (typically implemented as a balanced binary search tree) ensures all operations remain efficient with O(log n) complexity for insertions and removals.

Learn more about Sorting patterns.

Solution Approach

The solution uses a combination of a hash table and a sorted list to efficiently manage the leaderboard operations.

Data Structures:

• self.d: A defaultdict(int) that maps playerId to their current score. This provides O(1) access to any player's score.
• self.rank: A SortedList that maintains all player scores in sorted order. This allows efficient retrieval of top scores.

Implementation Details:

1. __init__ method:

   • Initializes an empty hash table d using defaultdict(int) to store player scores
   • Creates an empty SortedList called rank to maintain scores in sorted order

2. addScore(playerId, score) method:

   • First checks if the player exists in hash table d
   • If the player is new:
     • Adds the score directly to d[playerId]
     • Inserts the score into the sorted list rank
   • If the player already exists:
     • Removes the old score from rank using rank.remove(self.d[playerId])
     • Updates the player's score in the hash table by adding: self.d[playerId] += score
     • Inserts the new total score into rank using rank.add(self.d[playerId])
   • Time Complexity: O(log n) for sorted list operations

3. top(K) method:

   • Returns the sum of the K highest scores
   • Accesses the last K elements using self.rank[-K:] (since the list is sorted in ascending order, the largest values are at the end)
   • Uses Python's built-in sum() function to calculate the total
   • Time Complexity: O(K) for accessing and summing K elements

4. reset(playerId) method:

   • Removes the player's score from the sorted list using rank.remove()
   • Simultaneously removes the player from the hash table using d.pop(playerId), which returns the removed value
   • The returned value from pop() is used as the argument to remove() in a single line
   • Time Complexity: O(log n) for the sorted list removal

The SortedList data structure (from the sortedcontainers library) maintains elements in sorted order automatically, providing O(log n) insertion and removal operations through balanced tree implementations. This makes all leaderboard operations efficient even with a large number of players.

Example Walkthrough

Let's walk through a simple example to see how the leaderboard works:

Initial State:

• Hash table d = {}
• Sorted list rank = []

Step 1: addScore(1, 50)

• Player 1 doesn't exist in d
• Add to hash table: d = {1: 50}
• Add to sorted list: rank = [50]

Step 2: addScore(2, 30)

• Player 2 doesn't exist in d
• Add to hash table: d = {1: 50, 2: 30}
• Add to sorted list: rank = [30, 50] (automatically sorted)

Step 3: addScore(3, 70)

• Player 3 doesn't exist in d
• Add to hash table: d = {1: 50, 2: 30, 3: 70}
• Add to sorted list: rank = [30, 50, 70]

Step 4: top(2)

• Need sum of top 2 scores
• Access last 2 elements: rank[-2:] = [50, 70]
• Return sum: 50 + 70 = 120

Step 5: addScore(2, 40)

• Player 2 exists with score 30
• Remove old score from sorted list: rank.remove(30) → rank = [50, 70]
• Update hash table: d[2] = 30 + 40 = 70 → d = {1: 50, 2: 70, 3: 70}
• Add new score to sorted list: rank.add(70) → rank = [50, 70, 70]

Step 6: top(3)

• Access last 3 elements: rank[-3:] = [50, 70, 70]
• Return sum: 50 + 70 + 70 = 190

Step 7: reset(1)

• Remove from sorted list: rank.remove(50) → rank = [70, 70]
• Remove from hash table: d.pop(1) → d = {2: 70, 3: 70}

Final State:

• Hash table d = {2: 70, 3: 70}
• Sorted list rank = [70, 70]

This example demonstrates how the dual data structure approach efficiently handles all operations: the hash table provides quick player lookups while the sorted list maintains score ordering for fast top-K queries.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(): O(1) - Initializing empty data structures
• addScore(playerId, score):
  • If player doesn't exist: O(log n) for adding to SortedList
  • If player exists: O(n) for removing from SortedList + O(log n) for adding = O(n)
  • Overall: O(n) where n is the number of players
• top(K): O(K) for slicing and summing the last K elements
• reset(playerId): O(n) for removing from SortedList

Space Complexity:

• The dictionary self.d stores at most n player-score pairs: O(n)
• The SortedList self.rank stores at most n scores: O(n)
• Overall space complexity: O(n), where n is the number of players

This matches the reference answer that states the space complexity is O(n), where n is the number of players.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Score Updates in Sorted List

One of the most common mistakes is forgetting to remove the old score from the sorted list before adding the updated score when a player already exists. This leads to duplicate scores in the sorted list and incorrect results for the top(K) function.

Incorrect Implementation:

def addScore(self, playerId: int, score: int) -> None:
    # WRONG: Forgetting to remove old score
    self.player_scores[playerId] += score
    self.sorted_scores.add(self.player_scores[playerId])

Why it's wrong: Each time an existing player gets a score update, their new total is added to the sorted list without removing the old total. This causes:

• Multiple entries for the same player in the sorted list
• Inflated sums when calling top(K)
• Memory waste from storing obsolete scores

Correct Implementation:

def addScore(self, playerId: int, score: int) -> None:
    if playerId not in self.player_scores:
        self.player_scores[playerId] = score
        self.sorted_scores.add(score)
    else:
        # Must remove old score first
        self.sorted_scores.remove(self.player_scores[playerId])
        self.player_scores[playerId] += score
        self.sorted_scores.add(self.player_scores[playerId])

2. Race Condition Between Dictionary Update and Sorted List Update

Another pitfall is updating the dictionary before removing the old value from the sorted list, which makes it impossible to find the old score.

Incorrect Implementation:

def addScore(self, playerId: int, score: int) -> None:
    if playerId in self.player_scores:
        # WRONG: Dictionary updated first, old score is lost
        self.player_scores[playerId] += score
        self.sorted_scores.remove(self.player_scores[playerId])  # This removes the NEW score!
        self.sorted_scores.add(self.player_scores[playerId])

Why it's wrong: After updating player_scores[playerId], we lose access to the old score value. The remove() call will try to remove the new score (which isn't in the list yet), causing an error or unexpected behavior.

Correct Implementation:

def addScore(self, playerId: int, score: int) -> None:
    if playerId in self.player_scores:
        # Remove old score BEFORE updating dictionary
        self.sorted_scores.remove(self.player_scores[playerId])
        self.player_scores[playerId] += score
        self.sorted_scores.add(self.player_scores[playerId])

3. Using Regular List Instead of SortedList

Some developers might try to use a regular Python list and manually sort it, which severely impacts performance.

Incorrect Approach:

def __init__(self):
    self.player_scores = defaultdict(int)
    self.scores_list = []  # Regular list

def addScore(self, playerId: int, score: int) -> None:
    # ... update logic ...
    self.scores_list.append(new_score)
    self.scores_list.sort()  # O(n log n) every time!

Why it's wrong: Sorting the entire list after each insertion is O(n log n), making the solution inefficient for frequent updates. SortedList maintains order automatically with O(log n) insertions.

4. Misunderstanding Negative Indexing for Top K

Some might incorrectly use positive indexing to get top K scores, forgetting that SortedList maintains ascending order.

Incorrect Implementation:

def top(self, K: int) -> int:
    # WRONG: This gets the K LOWEST scores
    return sum(self.sorted_scores[:K])

Correct Implementation:

def top(self, K: int) -> int:
    # Use negative indexing to get K highest scores
    return sum(self.sorted_scores[-K:])