Leetcode 1244. Design A Leaderboard

Problem

You are tasked with implementing a leaderboard system for an online gaming tournament. The leaderboard must efficiently track player scores and support the following operations:

• addScore(playerId, score): Add points to a player's cumulative score. If the player doesn't exist, create a new entry for them.
• top(K): Return the sum of the scores of the top K players (players with the highest scores).
• reset(playerId): Clear a player's score, removing them from the leaderboard entirely.

Your implementation should handle frequent score updates and top-K queries efficiently.

Requirements

1. Implement a Leaderboard class with the three methods described above
2. Player scores are cumulative - calling addScore multiple times for the same player adds to their existing score
3. The top(K) method should return the sum of the K highest scores currently on the leaderboard
4. If there are fewer than K players, return the sum of all existing scores
5. The reset method completely removes a player's score from the leaderboard

Constraints

• 1 ≤ playerId ≤ 10^5
• 1 ≤ score ≤ 100
• 1 ≤ K ≤ total number of players
• At most 1000 total operations will be called
• All inputs are valid (no need to handle invalid player IDs in reset)

Examples

Example 1:

` Operations: addScore(1, 100) addScore(2, 80) addScore(3, 90) top(2)

Output: 190 Explanation: The top 2 scores are 100 (player 1) and 90 (player 3), sum = 190 `

Example 2:

` Operations: addScore(1, 50) addScore(1, 30) addScore(2, 60) top(1)

Output: 80 Explanation: Player 1's cumulative score is 80 (50 + 30), which is the highest `

Example 3:

` Operations: addScore(1, 100) addScore(2, 90) reset(1) top(2)

Output: 90 Explanation: After resetting player 1, only player 2's score of 90 remains `

Hint 1: Data Structure Choice Consider using a hash map to track each player's cumulative score. This allows O(1) updates for addScore and reset operations. For the top(K) query, you'll need to find the K largest values.

Hint 2: Optimizing top(K) For the top(K) operation, you could sort the scores each time (O(n log n)), or use a heap-based approach. Given the constraint of at most 1000 operations, a simple approach of sorting when needed is acceptable and easier to implement correctly.

Hint 3: Alternative Approach For more frequent queries, consider maintaining a sorted data structure like a TreeMap or using a max-heap. However, the simple hash map + sort approach is often sufficient and more straightforward for interview settings.

Full Solution ` class Leaderboard: def init(self): # Dictionary to store playerId -> cumulative score mapping self.scores = {}

def addScore(self, playerId: int, score: int) -> None:
    # Add score to existing player or create new entry
    if playerId in self.scores:
        self.scores[playerId] += score
    else:
        self.scores[playerId] = score

def top(self, K: int) -> int:
    # Sort all scores in descending order and sum top K
    sorted_scores = sorted(self.scores.values(), reverse=True)
    return sum(sorted_scores[:K])

def reset(self, playerId: int) -> None:
    # Remove player from leaderboard
    if playerId in self.scores:
        del self.scores[playerId]

`

Explanation:

The solution uses a hash map (dictionary) to maintain each player's cumulative score:

1. addScore: We check if the player exists. If they do, we add to their existing score; otherwise, we create a new entry. Time complexity: O(1).
2. top(K): We extract all score values, sort them in descending order, and sum the first K elements. Time complexity: O(n log n) where n is the number of players.
3. reset: We simply remove the player's entry from the dictionary. Time complexity: O(1).

Time Complexity:

• addScore: O(1)
• reset: O(1)
• top(K): O(n log n) where n is the number of players

Space Complexity: O(n) where n is the number of unique players on the leaderboard.

Alternative Optimization:

For scenarios with very frequent top(K) queries, you could maintain a sorted structure (like a balanced BST or using Python's sorted containers library). However, this adds complexity to addScore operations. The hash map + sort approach is optimal for this problem's constraints and provides a good balance between simplicity and performance.