Design A Leaderboard

Problem Description

Design a Leaderboard class that supports three operations:

1. addScore(playerId, score): Add the score to the given player's score. If the player does not exist, add them with the given score.
2. top(K): Return the sum of scores of the top K players.
3. reset(playerId): Reset the score of the specified player to 0.

The leaderboard starts empty.

Key Insights

• Use a hash table (dictionary) to maintain a mapping from playerId to their cumulative score.
• For the top(K) query, the simplest approach is to extract scores from the hash table and then compute the sum of the K highest scores.
• For top(K), one can either sort the scores or use a heap (priority queue) for efficiency.
• Given that there are at most 1000 operations and playerIds and K are bounded, a simple implementation suffices.

Space and Time Complexity

Time Complexity:

• addScore: O(1) per call.
• reset: O(1) per call.
• top(K): O(n log K) if using a heap or O(n log n) if sorting, where n is the number of players. Space Complexity:
• O(n) to store the player scores.

Solution

We maintain a dictionary that maps playerId to its current score. When addScore is called, update the player's score in the dictionary. When reset is called, set the player's score to 0 (or remove the player, but setting to 0 works as well since constraints guarantee valid calls). For the top(K) function, obtain all scores from the dictionary and then compute the sum of the top K scores by either sorting the scores in descending order or using a min-heap to efficiently track the K largest scores. This approach is straightforward and works well within the given constraints.

Code Solutions