Design A Leaderboard - Leetcode Solution

Problem Statement:

We need to design a Leaderboard class, which will have the following methods:

• void addScore(int playerId, int score): Insert a score into the leaderboard of a player.
• int top(int K): Return the score sum of the top K players.
• void reset(int playerId): Reset the score of a player. It is guaranteed that the player was added to the leaderboard before calling this function.

Solution:

We will solve this problem using a HashMap and a PriorityQueue. The HashMap will store the playerId and the corresponding score, while the PriorityQueue will store the top K players’ scores. Whenever we call the top(K) method, we will retrieve the top K players scores from the PriorityQueue, and sum them up to return the answer.

In the addScore() method, we will update the player's score in the HashMap. We will add the player's score if the player is not present in the HashMap, and update the score if the player is already present. After updating the score, we will remove the player’s score from the PriorityQueue as well, because we need to re-calculate the top K scores.

In the reset() method, we will remove the player's score from the HashMap and PriorityQueue because we need to recalculate the top K scores.

Code:

Let's start by creating a Player class with playerId and score attributes:

class Player{
    int playerId;
    int score;
    
    public Player(int playerId, int score){
        this.playerId = playerId;
        this.score = score;
    }
}

Now, let's implement the Leaderboard class:

class Leaderboard {
    Map<Integer, Integer> scores;
    PriorityQueue<Integer> topK;

    public Leaderboard() {
        scores = new HashMap<>();
        topK = new PriorityQueue<>((a, b) -> b - a); // Max heap
    }
    
    public void addScore(int playerId, int score) {
        int oldScore = scores.getOrDefault(playerId, 0);
        int newScore = oldScore + score;
        scores.put(playerId, newScore);

        topK.remove(oldScore); // Remove the old score
        topK.offer(newScore); // Add the new score
    }
    
    public int top(int K) {
        int sum = 0;
        for(int i=0; i<K; i++){
            if(topK.isEmpty()) break;
            sum += topK.poll();
        }
        return sum;
    }
    
    public void reset(int playerId) {
        int score = scores.get(playerId);
        scores.remove(playerId);
        topK.remove(score);
    }
}

The time complexity of this implementation will be O(log N) for addScore() and top() methods and O(1) for reset() method. The space complexity will be O(N), where N is the number of players.

1