MediumNo. 1244LeetCode Premium
Design A Leaderboard — LeetCode 1244 Python Solution
- Pattern
- Sorting
- Topics
- Design, Hash Table, Sorting
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Design a Leaderboard class, which has 3 functions: 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.
Example
- Input
- ["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
- Output
- [null,null,null,null,null,null,73,null,null,null,141]
- Explanation
- Leaderboard leaderboard = new Leaderboard ();
Python solution
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)Complexity
- Time
- O(log n)
- Space · auxiliary
- O(n)where n is the number of players
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1244. Design A Leaderboard is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1348 | Tweet Counts Per Frequency | Medium |
| 0049 | Group Anagrams | Medium |
| 0146 | LRU Cache | Medium |
| 0169 | Majority Element | Easy |
| 0208 | Implement Trie (Prefix Tree) | Medium |
| 0217 | Contains Duplicate | Easy |
Frequently asked questions
- How hard is LeetCode 1244. Design A Leaderboard?
LeetCode 1244. Design A Leaderboard is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1244. Design A Leaderboard?
The Python solution on this page runs in O(log n).
- What is the space complexity of LeetCode 1244. Design A Leaderboard?
The Python solution on this page uses O(n), where n is the number of players auxiliary space.
- What topics does LeetCode 1244. Design A Leaderboard cover?
LeetCode 1244. Design A Leaderboard is tagged Design, Hash Table and Sorting on LeetCode.
- Is LeetCode 1244. Design A Leaderboard a premium problem?
Yes. LeetCode 1244. Design A Leaderboard is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.