Problem Breakdown
We need to implement a dynamic data structure that manages scores for multiple players and supports three specific operations efficiently:
addScore(playerId, score): Increment an existing player’s total or initialize them if they don’t exist yet.top(K): Calculate the sum of the highestKcurrent scores in the system.reset(playerId): Remove a specific player from consideration (effectively setting their score to zero and excluding them).
Key Constraints & Edge Cases:
- Scale: Up to 10,000 players (
playerId) but only up to 1,000 total function calls. This suggests we don’t need highly optimized data structures like heaps or Fenwick trees for every operation; a standard dictionary with sorting is likely sufficient given the low call frequency relative to N. - Reset Guarantee: The problem guarantees
resetwill be called only if the player exists, so no error handling needed there (though defensive checks are safe). - Empty State: If
top(K)is called when fewer than K players exist (or leaderboard empty), we sum all available scores. Note that constraints say current number of players, so we never ask for more top items than exist.
Intuition
A brute-force approach would be to store the list in an array and sort it every time top(K) is called. However, since we need frequent updates (addScore, reset), maintaining a sorted list directly (like inserting into a BST) adds overhead ( or per update).
The Key Insight: We can separate concerns:
- Storage & Updates: Use a Hash Map (Python Dictionary) for O(1) access to store
playerId -> current_score. This handlesaddScoreandresetefficiently without touching the sorted structure immediately. - Querying (
top(K)): Since we only need the sum of top K scores, sorting the values from our dictionary is acceptable given the constraints (N=10k). Python’s Timsort is highly optimized for partially sorted data and runs in . With a maximum of 1,000 calls totop, total complexity remains well within limits.
If we were optimizing strictly for high-frequency updates vs queries on massive datasets (), we might consider heaps or segment trees, but here the dictionary + sort approach is cleaner and idiomatic in Python.
Approach
- Initialization: Create a class
Leaderboardwith an instance variable (e.g.,self.scores) initialized as an empty hash map ({}). addScore(playerId, score):- Check if
playerIdexists in the dictionary using.get(). - If it does not exist, initialize with
score. - If it exists, add
scoreto the existing value (self.scores[playerId] += score).
- Check if
reset(playerId):- Remove the key from the dictionary using
.pop(). This effectively removes them from future sums and keeps memory usage proportional to active players.
- Remove the key from the dictionary using
top(K):- Extract all current scores into a list:
list(self.scores.values()). - Sort this list in descending order (
reverse=True). - Sum the first
Kelements using slicing or iteration. Return the sum (defaulting to 0 if empty, though constraints ensure K is valid).
- Extract all current scores into a list:
Complexity Analysis
- Time Complexity:
addScore: average case for dictionary operations.reset: amortized with.pop().top(K): Sorting takes where is the number of active players (). With a maximum of 1,000 calls to this method across all test cases (implied by “at most 1000 function calls”), total operations are roughly proportional to acceptable limits for Python.
- Space Complexity: where is the number of unique players stored in the dictionary.
Solution
class Leaderboard:
def __init__(self):
self.scores = {} # Dictionary mapping playerId -> current total score
def addScore(self, playerId: int, score: int) -> None:
if playerId not in self.scores:
self.scores[playerId] = score
else:
self.scores[playerId] += score
def top(self, K: int) -> int:
# Extract current scores and sort descending to get highest first
sorted_scores = sorted(list(self.scores.values()), reverse=True)
# Sum the top K elements.
# Constraints guarantee K <= len(sorted_scores), so slicing is safe.
return sum(sorted_scores[:K])
def reset(self, playerId: int) -> None:
if playerId in self.scores:
del self.scores[playerId]
Edge Cases Handled
- New Player:
addScorehandles initialization via the dictionary’s default behavior (check existence before adding). - Existing Player Update: Logic correctly increments existing scores rather than overwriting.
- Reset Guarantee: The prompt guarantees a player exists for reset; using
.pop()or explicit deletion removes them cleanly from memory and logic without needing to check if they exist first in the implementation (though checking is safer generally). - Top K Summation: Slicing
[:K]handles cases where fewer than K players might theoretically remain, though constraints prevent this. It returns 0 for empty lists naturally via Python’s sum behavior on an empty sequence.