MediumHash TableDesignSortingHeap (Priority Queue)

Design a Leaderboard

1 approach, code in every language

Design a leaderboard for a game where every player has a running total score. Players are identified by an integer id, and their score accumulates as they play.

Implement a Leaderboard class that supports three operations:

addScore(playerId, score): Add the given score to the player's cumulative total. If the player is not yet on the board, register them with a starting score of 0 and then add the given score.

top(K): Return the sum of the K highest cumulative scores currently on the board.

reset(playerId): Reset the given player's cumulative score back to 0. It is guaranteed that the player exists when reset is called.

Initially the leaderboard is empty.

Example 1

Input: Leaderboard(); addScore(1, 73); addScore(2, 56); addScore(3, 39); addScore(4, 51); addScore(5, 4); top(1); reset(1); reset(2); addScore(2, 51); top(3);

Output: 73, 141

After the five addScore calls the totals are {1:73, 2:56, 3:39, 4:51, 5:4}. top(1) returns the single largest total, 73. After resetting players 1 and 2 to 0 and adding 51 to player 2, the totals are {1:0, 2:51, 3:39, 4:51, 5:4}. top(3) sums the three largest totals: 51 + 51 + 39 = 141.

Example 2

Input: Leaderboard(); addScore(1, 10); addScore(1, 20); top(1); reset(1); top(1);

Output: 30, 0

Two addScore calls on player 1 accumulate to 30, so top(1) is 30. After reset(1) the player's total is 0, so top(1) sums the single largest total, which is now 0.

Constraints

1 <= playerId, K <= 10^4
It is guaranteed that K is less than or equal to the current number of players.
1 <= score <= 100
At most 10^4 function calls will be made across addScore, top, and reset.

Hash Map + Sort On Demand

Store cumulative scores in a hash map keyed by playerId, then sort or heap-select the values only when top(K) is called.

Loading animation…

Intuition

The write-heavy operations, addScore and reset, only touch a single player, so a hash map from playerId to cumulative score makes them constant time. The only expensive operation is top(K), which needs the K largest values. Rather than keeping the scores sorted at all times, we sort (or heap-select) on demand when top is actually requested. This is the classic sort-on-demand versus always-sorted tradeoff: a balanced tree or an indexed sorted structure would give O(log n) top-K reads but forces every addScore/reset to pay O(log n) to keep the structure ordered. Since scores change far more often than the leaderboard is queried in typical workloads, paying O(n log n) or O(n log K) only at query time keeps the common path cheap. If top(K) were the dominant call instead, a balanced BST keyed by score (or an order-statistics tree) would be the better choice.

Algorithm walkthrough

1Keep a hash map scores mapping playerId to that player's cumulative score; it starts empty.
2For addScore(playerId, score), look up the player's current total (treating a missing player as 0) and add score to it, writing the new total back into the map.
3For reset(playerId), set the player's entry to 0 (or delete it), since the problem guarantees the player exists.
4For top(K), copy all current score values into a list.
5Sort that list in descending order, or use a size-K min-heap / partial selection to find the K largest values.
6Sum the first K values from the sorted list (or the heap contents) and return that sum.

Implementation

import heapq


class Leaderboard:
    def __init__(self):
        self.scores = {}

    def addScore(self, playerId: int, score: int) -> None:
        self.scores[playerId] = self.scores.get(playerId, 0) + score

    def top(self, K: int) -> int:
        # nlargest uses a size-K heap internally: O(n log K).
        return sum(heapq.nlargest(K, self.scores.values()))

    def reset(self, playerId: int) -> None:
        self.scores[playerId] = 0

Time

addScore and reset are O(1) average; top(K) is O(n log K) with a size-K heap or O(n log n) with a full sort, where n is the number of players.

Space

O(n) for the hash map, plus O(n) scratch space when top copies the score values.

A balanced BST keyed by score would make top(K) faster to read but would slow every addScore/reset to O(log n); sort-on-demand favors the write-heavy common path.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free