Design a Leaderboard

Problem description

Design a Leaderboard class, which has 3 functions:

1. addScore(playerId, score): Update the leaderboard by adding score to the given player’s score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.
2. top(K): Return the score sum of the top K players.
3. 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.

Constraints

1. 1 <= playerId, K <= 10000
2. It’s guaranteed that K is less than or equal to the current number of players.
3. 1 <= score <= 100
4. There will be at most 1000 function calls.

Solution

1. It is easy to see that we need to have a map to keep a key-value relationship of playerId and score. So whether for function addScore(playerId, score) or reset(playerId), we can easily to set or erase(also we can set to 0, but for better performance) the score of each player.
2. The core problem is top(K) function, which requires us to the sum score. Due to the contraints lots of function calls, we need to assure that top(K) function $\leq O(logn)$ rather than a linear time complexity. This constraint requires us for another data structure of $O(logn)$ to store the scores. In most cases, this data structure needs to be another map for score and player, but multiple scores in this case, so the value of the map needs to be an array, which makes us to design an another data structure to store the index of players in this array(reduce search time complexity). So for the scores, we will have a sorted set to store it.

Cpp

There is a multiset data structure that can save same values and also is a sorted data structure, which meets our requirements.

We keep an unordered_map player_score to save the playerId and score. And for a sorted multiset to store the scores.

unordered_map<int,int> player_score;
multiset<int> scores;

For reset(playerId) function, we set a multiset.find to get the index of one of this score. And we erase this score and the player.

void reset(int playerId) {
    auto it = scores.find(player_score[playerId]);
    scores.erase(it);
    player_score.erase(playerId);
}

For remnant part, it is quick and easy to see. Let’s show all of it.

class Leaderboard {
public:
    Leaderboard() {}
    
    void addScore(int playerId, int score) {
        if(player_score.find(playerId)!=player_score.end()){
            score += player_score[playerId];
            reset(playerId);
        }
        player_score[playerId] = score;
        scores.insert(score);
    }
    
    int top(int K) {
        int sum = 0;
        for(auto it=scores.rbegin();K>0;K--,it++){
            sum += *it;
        }
        return sum;
    }
    
    void reset(int playerId) {
        auto it = scores.find(player_score[playerId]);
        scores.erase(it);
        player_score.erase(playerId);
    }
  
private:
    unordered_map<int,int> player_score;
    multiset<int> scores;
};

The problem is cited from Leetcode 1244. Design A Leaderboard. And the solution is cited from mtobeiyf —— C++ Multiset + Map Solution.