917. Leaderboard Desk
A quiz arcade keeps a live scoreboard. Build the class Leaderboard (no constructor arguments); at the start the board is empty.
addScore(playerId, score)addsscorepoints to that player's running total. A player who is not yet on the board joins it with total 0 before the points are added.top(k)returns the sum of theklargest totals among players currently on the board. If fewer thankplayers are on the board, return the sum of all their totals; an empty board gives 0.reset(playerId)removes the player from the board, so a later score starts again from 0. If the player is not on the board, nothing happens.
Do not re-sort the whole board on every call: an update should need only a binary search, and top should cost O(k).
Example 1
- Input:
- operations = ["Leaderboard","addScore","addScore","addScore","top","top","reset","top"]arguments = [[],[41,30],[17,12],[41,5],[1],[2],[41],[2]]
- Output:
- [null,null,null,null,35,47,null,12]
- Explanation:
Player 41 totals 35 and player 17 totals 12, so top 1 is 35 and top 2 is 47. After player 41 is reset only 12 remains.
Example 2
- Input:
- operations = ["Leaderboard","addScore","addScore","addScore","top","addScore","top"]arguments = [[],[9,8],[8,8],[7,8],[5],[7,1],[1]]
- Output:
- [null,null,null,null,24,null,9]
- Explanation:
Three players tie on 8, so asking for five just sums all three (24); then player 7 reaches 9 and leads.
Constraints
1 ≤ playerId ≤ 100000
1 ≤ score ≤ 1000
1 ≤ k ≤ 100000
At most 3000 calls in total
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(log n + shift) per update, O(k) per top
- Space
- O(n)