Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1244.html
1244. Design A Leaderboard
Level
Medium
Description
Design a Leaderboard class, which has 3 functions:
addScore(playerId, score): Update the leaderboard by addingscoreto the given player’s score. If there is no player with such id in the leaderboard, add him to the leaderboard with the givenscore.top(K): Return the score sum of the topKplayers.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.
Initially, the leaderboard is empty.
Example 1:
Input:
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[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 leaderboard = new Leaderboard ();
leaderboard.addScore(1,73); // leaderboard = [[1,73]];
leaderboard.addScore(2,56); // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39); // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51); // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4); // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1); // returns 73;
leaderboard.reset(1); // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2); // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51); // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3); // returns 141 = 51 + 51 + 39;
Constraints:
1 <= playerId, K <= 10000- It’s guaranteed that
Kis less than or equal to the current number of players. 1 <= score <= 100- There will be at most
1000function 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; public Leaderboard() { playerIDs = new ArrayList<Integer>(); scores = new ArrayList<Integer>(); size = 0; } public void addScore(int playerId, int score) { if (size == 0) { playerIDs.add(playerId); scores.add(score); } 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; playerIDs.add(index, playerId); scores.add(index, newScore); } else { int index = binarySearch(scores, score); if (index < 0) index = -index - 1; playerIDs.add(index, playerId); scores.add(index, score); } } 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; } } /** * Your Leaderboard object will be instantiated and called as such: * Leaderboard obj = new Leaderboard(); * obj.addScore(playerId,score); * int param_2 = obj.top(K); * obj.reset(playerId); */MaxHeap
-
// OJ: https://leetcode.com/problems/design-a-leaderboard/ // Time: // Leaderboard: O(1) // addScore: O(1) // top: O(NlogK) // reset: O(1) // Space: O(N + K) class Leaderboard { unordered_map<int, int> m; public: Leaderboard() {} 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 class Leaderboard: 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 self.rank.add(score) else: self.rank.remove(self.d[playerId]) self.d[playerId] += score self.rank.add(self.d[playerId]) def top(self, K: int) -> int: return sum(self.rank[-K:]) def reset(self, playerId: int) -> None: self.rank.remove(self.d.pop(playerId)) # Your Leaderboard object will be instantiated and called as such: # obj = Leaderboard() # obj.addScore(playerId,score) # param_2 = obj.top(K) # obj.reset(playerId)