Design A Leaderboard

How it works

Instead of sorting all N scores, we can use a min-heap of size K to find the top K scores more efficiently. As we iterate through all scores, we maintain a heap containing the K largest scores seen so far. When the heap exceeds size K, we remove the smallest element. After processing all scores, the heap contains exactly the top K scores, and we sum them up.

Steps

1. Use a hash map scores to store the mapping from playerId to their score.
2. For addScore(playerId, score): if the player exists, add to their score; otherwise, initialize and add.
3. For top(K):
   • Create a min-heap.
   • For each score value, push it onto the heap. If the heap size exceeds K, pop the minimum.
   • After processing all scores, sum up all elements remaining in the heap.
4. For reset(playerId): set the player's score to 0 in the hash map.

Complexity

• Time complexity:

  • O(1) for addScore
  • O(1) for reset
  • O(N log K) for top

• Space complexity: O(N + K)

Where N is the total number of players in the leaderboard, and K is the number of top-scoring players.

Things to watch for

Using Reset to Delete vs. Set to Zero

The reset function should remove the player's score entirely or set it to zero, depending on the problem requirements. Using the wrong approach affects how the top(K) calculation handles that player.

Forgetting to Handle Duplicate Scores in TreeMap

When using a TreeMap to track scores, multiple players can have the same score. You must store a count of players per score, not just a single player. Otherwise, adding a second player with the same score will overwrite the first.

Not Updating Both Data Structures When Score Changes

When a player's score changes via addScore, you must update both the player-to-score mapping and the sorted scores structure. Forgetting to remove the old score from the sorted structure leads to stale data.

import heapq

class Leaderboard:

    def __init__(self):
        self.scores = {}

    def addScore(self, playerId: int, score: int) -> None:
        if playerId not in self.scores:
            self.scores[playerId] = 0
        self.scores[playerId] += score

    def top(self, K: int) -> int:
    
        # This is a min-heap by default in Python.
        heap = []
        for x in self.scores.values():
            heapq.heappush(heap, x)
            if len(heap) > K:
                heapq.heappop(heap)
        res = 0
        while heap:
            res += heapq.heappop(heap)
        return res

    def reset(self, playerId: int) -> None:
        self.scores[playerId] = 0

class Leaderboard {
private:
    unordered_map<int, int> scores;
    
public:
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        if (scores.find(playerId) == scores.end()) {
            scores[playerId] = 0;
        }
        scores[playerId] += score;
    }
    
    int top(int K) {
        // By default, priority_queue is max-heap, so we use greater<int> for min-heap
        priority_queue<int, vector<int>, greater<int>> heap;
        
        for (const auto& entry : scores) {
            heap.push(entry.second);
            if (heap.size() > K) {
                heap.pop();
            }
        }
        
        int total = 0;
        while (!heap.empty()) {
            total += heap.top();
            heap.pop();
        }
        return total;
    }
    
    void reset(int playerId) {
        scores[playerId] = 0;
    }
};