##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1244.html

Medium

## 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. 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],,,,[2,51],]
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.

## Solution

#### Quick sort

Maintain two lists that store players and scores respectively, and maintain size that represents the number of players that have score greater than 0. At any time, the elements in the scores list are sorted in descending order. For index i such that 0 <= i < size, the element at index i in the players list is the id of the player that ranks i-th, and the element at index i in the scores list is the player’s score.

For the constructor, initialize the two lists and initialize size to 0.

For addScore(playerId, score), if size == 0, then simply add playerId and score to the lists. Otherwise, if playerId is in the players list, then calculate the player’s new score, remove the previous player id and the previous score from both lists, use binary search to find the insertion index of the new score, and add playerId and score at the insertion index in the lists. If playerId is not in the players list, then use binary search to find the insertion index of score, and add playerId and score at the insertion index in the lists.

For top(K), calculate the sum of the first K elements of the scores list, and return. If K > size, then calculate the sum of all the elements of the scores list, and return.

For reset(playerId), find the index index of playerId in the players list, and remove the elements at index index from both lists.

• class Leaderboard {
List<Integer> playerIDs;
List<Integer> scores;
int size;

playerIDs = new ArrayList<Integer>();
scores = new ArrayList<Integer>();
size = 0;
}

public void addScore(int playerId, int score) {
if (size == 0) {
} else {
int idIndex = playerIDs.indexOf(playerId);
if (idIndex >= 0) {
int newScore = scores.get(idIndex) + score;
playerIDs.remove(idIndex);
scores.remove(idIndex);
int index = binarySearch(scores, newScore);
if (index < 0)
index = -index - 1;
} else {
int index = binarySearch(scores, score);
if (index < 0)
index = -index - 1;
}
}
size++;
}

public int top(int K) {
K = Math.min(K, size);
int sum = 0;
for (int i = 0; i < K; i++)
sum += scores.get(i);
return sum;
}

public void reset(int playerId) {
int index = playerIDs.indexOf(playerId);
playerIDs.remove(index);
scores.remove(index);
size--;
}

public int binarySearch(List<Integer> list, int key) {
int size = list.size();
int low = 0, high = size - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int num = list.get(mid);
if (num == key)
return mid;
else if (num > key)
low = mid + 1;
else
high = mid - 1;
}
return -low - 1;
}
}

/**
* int param_2 = obj.top(K);
* obj.reset(playerId);
*/


#### MaxHeap

• // OJ: https://leetcode.com/problems/design-a-leaderboard/
// Time:
//      top: O(NlogK)
//      reset: O(1)
// Space: O(N + K)
unordered_map<int, int> m;
public:
void addScore(int playerId, int score) {
m[playerId] += score;
}
int top(int K) {
priority_queue<int, vector<int>, greater<>> pq;
for (auto &[id, score] : m) {
pq.push(score);
if (pq.size() > K) pq.pop();
}
int ans = 0;
while (pq.size()) {
ans += pq.top();
pq.pop();
}
return ans;
}
void reset(int playerId) {
m[playerId] = 0;
}
};

• from sortedcontainers import SortedList

def __init__(self):
self.d = defaultdict(int)
self.rank = SortedList()

def addScore(self, playerId: int, score: int) -> None:
if playerId not in self.d:
self.d[playerId] = score
else:
self.rank.remove(self.d[playerId])
self.d[playerId] += score

def top(self, K: int) -> int:
return sum(self.rank[-K:])

def reset(self, playerId: int) -> None:
self.rank.remove(self.d.pop(playerId))