⚡Flashcard Drill➔
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

  1. Keep a single hash map from player id to cumulative score. addScore and reset are then O(1).
  2. top(K) sorts the scores in descending order and sums the first K.
  3. The K guarantee (K <= number of players) means no bounds handling is needed.
  4. 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=True with [:K] is clearer and equally fast.
  • Optimising top prematurely: 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems