Problem
Design a Leaderboard class, which has 3 functions:
addScore(playerId, score)
: Update the leaderboard by addingscore
to the given player’s score. If there is no player with such id in the leaderboard, add him to the leaderboard with the givenscore
.top(K)
: Return the score sum of the topK
players.reset(playerId)
: Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.
Initially, the leaderboard is empty.
Examples
Example 1:
|
|
Constraints:
1 <= playerId, K <= 10000
- It’s guaranteed that
K
is less than or equal to the current number of players. 1 <= score <= 100
- There will be at most
1000
function calls.
Solution
Method 1 – Hash Map and Sorting for Top K
Intuition
We need to efficiently update player scores, get the sum of top K scores, and reset scores. A hash map allows fast updates and lookups, and sorting the values allows us to get the top K scores easily (acceptable for up to 1000 calls and 10,000 players).
Approach
- Use a hash map to store playerId to score mapping.
- For
addScore
, add the score to the player’s current score (or set if new). - For
top(K)
, get all scores, sort them in descending order, and sum the top K. - For
reset
, remove the player from the map.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n)
fortop(K)
, wheren
is the number of players, due to sorting.O(1)
foraddScore
andreset
. - 🧺 Space complexity:
O(n)
, for storing player scores.