# Solution For Design A Leaderboard

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:

“`
Map scores;
PriorityQueue 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.

## Step by Step Implementation For Design A Leaderboard

```/*

Design a Leaderboard class, which has following functions:

addScore(playerId, score): Update the leaderboard by adding score to the given player's record. If there is no record for the player, create one with the given player's id and score.

top(K): Return the score sum of the top K players.

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.

Example 1:

Input:
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output:
[null,null,null,null,null,null,73,null,null,null,141]

Explanation:
leaderboard.top(3);           // returns 141 = 51 + 51 + 39;

Constraints:

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

Map map;

map = new HashMap<>();
}

public void addScore(int playerId, int score) {
if(map.containsKey(playerId)) {
map.put(playerId, map.get(playerId) + score);
} else {
map.put(playerId, score);
}
}

public int top(int K) {
PriorityQueue pq = new PriorityQueue<>();
for(int key : map.keySet()) {
}
int sum = 0;
for(int i = 0; i < K; i++) {
sum += pq.poll();
}
return sum;
}

public void reset(int playerId) {
map.put(playerId, 0);
}
}

/**
* int param_2 = obj.top(K);
* obj.reset(playerId);
*/```
`This problem can be solved using a min heap. We can keep track of the top K players in the heap, and every time a new player's score is added, we can compare it to the minimum score in the heap. If the new score is higher, we can remove the minimum score from the heap and add the new score. In this way, we can always maintain a heap of size K with the top K scores.`
```var Leaderboard = function() {
// create a map to store the players and their scores
this.players = new Map();
};

/**
* @param {number} playerId
* @param {number} score
* @return {void}
*/
// if the player is not in the map, add them with a score of 0
if (!this.players.has(playerId)) {
this.players.set(playerId, 0);
}

// update the player's score
this.players.set(playerId, this.players.get(playerId) + score);
};

/**
* @param {number} K
* @return {number[]}
*/
// create an array to store the top K players
const topPlayers = [];

// iterate through the map and push the players into the array in order from highest to lowest score
for (const [player, score] of this.players) {
topPlayers.push({ player, score });
}

topPlayers.sort((a, b) => b.score - a.score);

// return an array of the player ids
};

/**
* @param {number} playerId
* @return {void}
*/
// remove the player from the map
this.players.delete(playerId);
};```
```#include
#include
#include
#include
using namespace std;

public:
map hash;
vector scores;

hash.clear();
scores.clear();
}

void addScore(int playerId, int score) {
if(hash.find(playerId) == hash.end()) {
hash[playerId] = score;
scores.push_back(score);
}
else {
hash[playerId] += score;
}
}

int top(int K) {
sort(scores.begin(), scores.end(), greater());
int sum = 0;
for(int i = 0; i < K; i++) {
sum += scores[i];
}
return sum;
}

void reset(int playerId) {
hash.erase(playerId);
}
};

/**
* int param_2 = obj->top(K);
* obj->reset(playerId);
*/```
```using System;
using System.Collections.Generic;

// create a dictionary to store players and their scores
Dictionary dictionary = new Dictionary();

// add a new score for a player
public void AddScore(int playerId, int score) {

// if the player is not in the dictionary, add them
if(!dictionary.ContainsKey(playerId)) {
}
// otherwise, update their score
else {
dictionary[playerId] = score;
}
}

// get the current top score
public int GetCurrentTopScore() {

// set the default to the lowest possible score
int currentTopScore = Int32.MinValue;

// loop through all the players in the dictionary
foreach(KeyValuePair player in dictionary) {

// if the player's score is higher than the current top score, update it
if(player.Value > currentTopScore) {
currentTopScore = player.Value;
}
}

// return the current top score
return currentTopScore;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]