1098. Rank Board
An arcade leaderboard stores the scores of players who are currently online. Scores come and go all the time, and the display wants to show, for any score, how many players are doing strictly better. Design RankBoard, a multiset of integer scores that can answer this quickly.
insert(score)adds one copy ofscore. The same score may be inserted many times.erase(score)removes exactly one copy ofscoreif at least one is stored; otherwise it does nothing.countGreater(score)returns how many stored copies are strictly greater thanscore. The queried score need not be stored.
Keeping a plain list and counting on every query, or re-sorting after each change, is too slow when the board is large and busy.
Example 1
- Input:
- operations = ["RankBoard","insert","insert","insert","countGreater","countGreater","erase","countGreater","countGreater"]arguments = [[],[50],[80],[50],[50],[49],[50],[49],[80]]
- Output:
- [null,null,null,null,1,3,null,2,0]
- Explanation:
Only 80 is strictly above 50; above 49 sit both 50s and the 80 (3 copies); erasing one 50 leaves 2 above 49.
Example 2
- Input:
- operations = ["RankBoard","countGreater","erase","insert","countGreater","countGreater","erase","erase","countGreater"]arguments = [[],[0],[7],[-5],[-6],[-5],[-5],[-5],[-6]]
- Output:
- [null,0,null,null,1,0,null,null,0]
- Explanation:
Queries on an empty board give 0, erasing a missing score changes nothing, and the second erase of -5 finds nothing to remove.
Constraints
1 ≤ number of operations ≤ 2 * 105
-109 ≤ score ≤ 109
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) per operation
- Space
- O(n)