Design A Leaderboard
Design A Leaderboard is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (hash map + size-k min-heap), runs in O(1) for addScore and reset, O(n log K) for top time and O(n + K) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort all totals on every top) up.
Problem
Design a Leaderboard that tracks a total score for each player.
Leaderboard()starts with an empty board.void addScore(int playerId, int score)addsscoreto that player’s total. A player who is not on the board yet joins with a total ofscore.int top(int K)returns the sum of theKhighest totals currently on the board.void reset(int playerId)removes the player from the board (their total goes back to0). If they score again later, they rejoin as a new player.
Examples
Example 1
- Input
Leaderboard(), addScore(3, 40), addScore(8, 15), addScore(5, 60), top(2), addScore(8, 50), top(2), reset(5), top(2)- Output
100, 125, 105- Why
- First the two best are 60 + 40. Player 8 climbs to 65, so the top two become 65 + 60. After player 5 is reset, the top two are 65 + 40.
Example 2
- Input
Leaderboard(), addScore(1, 7), addScore(2, 7), addScore(1, 3), top(1), reset(1), addScore(1, 2), top(2)- Output
10, 9- Why
- Player 1 reaches 10 and leads. After the reset player 1 restarts at 2, so the top two are 7 + 2.
Constraints
1 <= playerId, K <= 10^41 <= score <= 100Kis never larger than the number of players currently on the board.resetis only called for a player who is on the board.- At most
1000calls in total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (sort all totals on every top) | O(1) for addScore and reset, O(n log n) for top | O(n) |
| Optimal (hash map + size-K min-heap) | O(1) for addScore and reset, O(n log K) for top | O(n + K) |
1Brute force (sort all totals on every top)
O(1) for addScore and reset, O(n log n) for topSorting the totals of all n players dominates top.O(n)The map plus a temporary copy of the totals.Keep a map from player to total. For top(K), copy all totals into a list, sort it in descending order and add up the first K.
- addScore: scores[id] += score (starting from 0).
- reset: remove id from the map.
- top(K): sort all values descending and sum the first K.
class Leaderboard {
private final Map<Integer, Integer> scores = new HashMap<>();
public Leaderboard() {}
public void addScore(int playerId, int score) {
scores.merge(playerId, score, Integer::sum);
}
public int top(int K) {
List<Integer> all = new ArrayList<>(scores.values());
all.sort(Collections.reverseOrder());
int sum = 0;
for (int i = 0; i < K; i++) sum += all.get(i);
return sum;
}
public void reset(int playerId) {
scores.remove(playerId);
}
}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:
return sum(sorted(self.scores.values(), reverse=True)[:K])
def reset(self, playerId: int) -> None:
del self.scores[playerId]class Leaderboard {
unordered_map<int, int> scores;
public:
Leaderboard() {}
void addScore(int playerId, int score) {
scores[playerId] += score;
}
int top(int K) {
vector<int> all;
for (auto& [id, s] : scores) all.push_back(s);
sort(all.begin(), all.end(), greater<int>());
int sum = 0;
for (int i = 0; i < K; i++) sum += all[i];
return sum;
}
void reset(int playerId) {
scores.erase(playerId);
}
};class Leaderboard {
constructor() {
this.scores = new Map();
}
addScore(playerId, score) {
this.scores.set(playerId, (this.scores.get(playerId) || 0) + score);
}
top(K) {
const all = [...this.scores.values()].sort((a, b) => b - a);
let sum = 0;
for (let i = 0; i < K; i++) sum += all[i];
return sum;
}
reset(playerId) {
this.scores.delete(playerId);
}
}2Optimal (hash map + size-K min-heap)
O(1) for addScore and reset, O(n log K) for topEach of the n totals costs one push and at most one pop on a heap of size K.O(n + K)The map of n players and a heap of at most K + 1 values.The map still gives O(1) updates. For top(K), push every total into a min-heap and pop whenever it grows past K. The heap then holds exactly the K largest totals, and their sum is the answer. This avoids sorting all players when K is small.
- addScore and reset update the map as before.
- top(K): for each total, push it onto a min-heap; if the heap size exceeds K, pop the smallest.
- Pop everything left in the heap and return the sum.
class Leaderboard {
private final Map<Integer, Integer> scores = new HashMap<>();
public Leaderboard() {}
public void addScore(int playerId, int score) {
scores.merge(playerId, score, Integer::sum);
}
public int top(int K) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int s : scores.values()) {
heap.offer(s);
if (heap.size() > K) heap.poll();
}
int sum = 0;
while (!heap.isEmpty()) sum += heap.poll();
return sum;
}
public void reset(int playerId) {
scores.remove(playerId);
}
}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:
heap = []
for s in self.scores.values():
heapq.heappush(heap, s)
if len(heap) > K:
heapq.heappop(heap)
return sum(heap)
def reset(self, playerId: int) -> None:
del self.scores[playerId]class Leaderboard {
unordered_map<int, int> scores;
public:
Leaderboard() {}
void addScore(int playerId, int score) {
scores[playerId] += score;
}
int top(int K) {
priority_queue<int, vector<int>, greater<int>> heap;
for (auto& [id, s] : scores) {
heap.push(s);
if ((int)heap.size() > K) heap.pop();
}
int sum = 0;
while (!heap.empty()) {
sum += heap.top();
heap.pop();
}
return sum;
}
void reset(int playerId) {
scores.erase(playerId);
}
};class MinHeap {
constructor() { this.a = []; }
size() { return this.a.length; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p] <= a[i]) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && a[l] < a[m]) m = l;
if (r < a.length && a[r] < a[m]) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
class Leaderboard {
constructor() {
this.scores = new Map();
}
addScore(playerId, score) {
this.scores.set(playerId, (this.scores.get(playerId) || 0) + score);
}
top(K) {
const heap = new MinHeap();
for (const s of this.scores.values()) {
heap.push(s);
if (heap.size() > K) heap.pop();
}
let sum = 0;
while (heap.size() > 0) sum += heap.pop();
return sum;
}
reset(playerId) {
this.scores.delete(playerId);
}
}Edge cases to test
- Ties: several players with the same total, all of them counted
- A player who is reset and later added again starts from the new score
- top(K) where K equals the number of players on the board
Hints
Hint 1
A hash map from player to total score makes addScore and reset O(1).
Hint 2
For top(K) you only need the K largest totals, not the full order.
Hint 3
A min-heap that never holds more than K values keeps exactly the K largest seen so far.
FAQ
What is the best time complexity for Design A Leaderboard?
Optimal (hash map + size-K min-heap) runs in O(1) for addScore and reset, O(n log K) for top time and O(n + K) extra space. Each of the n totals costs one push and at most one pop on a heap of size K.
Which pattern does Design A Leaderboard use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Design A Leaderboard?
Yes. Brute force (sort all totals on every top) takes O(1) for addScore and reset, O(n log n) for top time and O(n) space. Keep a map from player to total.
Which edge cases should I test for Design A Leaderboard?
Ties: several players with the same total, all of them counted; A player who is reset and later added again starts from the new score; top(K) where K equals the number of players on the board.