NeetCode #34LC-1244MediumArrays & HashingNC Algo100
← Back to All Problems#34 · #1244 · Design A Leaderboard(力扣排行榜)
📌 Problem Statement & Constraints
Design a leaderboard with
addScore(playerId, score), top(K) returning the sum of the top K scores, and reset(playerId) setting that player's score to 0. Constraints: at most 1000 players and 10^4 calls; 1 <= score <= 100, 1 <= K <= number of players.💡 Core Algorithmic Approaches
- Keep a single hash map from player id to cumulative score.
addScoreandresetare then O(1). top(K)sorts the scores in descending order and sums the firstK.- The
Kguarantee (K <= number of players) means no bounds handling is needed. - This is the straightforward design the problem asks for. A follow-up might demand O(log n)
top, which would call for a balanced BST or a Fenwick tree over score buckets -- worth mentioning as the scaling path.
💻 Benchmark Python3 Implementation
class Leaderboard:
def __init__(self):
from collections import defaultdict
self.scores = defaultdict(int) # playerId -> total score
def addScore(self, playerId: int, score: int) -> None:
self.scores[playerId] += score # accumulate
def top(self, K: int) -> int:
return sum(sorted(self.scores.values(), reverse=True)[:K])
def reset(self, playerId: int) -> None:
self.scores[playerId] = 0
# Scaling variant: keep a Fenwick tree over score buckets so top(K) is O(log V)
class Leaderboard2:
def __init__(self):
self.scores = {}
self.freq = [0] * 100001 # freq[s] = how many players have score s
self.bit = [0] * 100002 # BIT over freq, storing s * freq[s]
def _upd(self, s: int, delta: int) -> None:
i = s + 1
while i < len(self.bit):
self.bit[i] += delta
i += i & -i
def addScore(self, playerId: int, score: int) -> None:
old = self.scores.get(playerId, 0)
if old:
self._upd(old, -old)
self.scores[playerId] = old + score
self._upd(old + score, old + score)
def reset(self, playerId: int) -> None:
old = self.scores.get(playerId, 0)
if old:
self._upd(old, -old)
self.scores[playerId] = 0
def top(self, K: int) -> int:
# walk score buckets from high to low, taking min(remaining, freq)
res = 0
s = 100000
while K > 0 and s > 0:
take = min(K, self.freq[s])
res += take * s
K -= take
s -= 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) for addScore and reset, O(P log P) for top where P is the number of players. The Fenwick variant makes all three O(log V) but needs freq maintenance, shown here for completeness.
💾 Space Complexity
O(P) for the score map, where P is the number of distinct players.
⚠️ Interview Pitfalls & Follow-ups
- Overwriting instead of accumulating in
addScore: a player may be scored several times, so the scores must be summed. - Deleting the entry in
reset: setting the score to 0 is required so the player still counts as a participant with score 0. - Sorting ascending and slicing from the end: it works but
reverse=Truewith[:K]is clearer and equally fast. - Optimising
topprematurely: with only 1000 players, the sort is fine. Mention the Fenwick tree only if the interviewer asks about scaling.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.