Design A Leaderboard

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.
top(K): Return the score sum of the top K players.
reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.

Initially, the leaderboard is empty.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


Input:
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output:
[null,null,null,null,null,null,73,null,null,null,141]
Explanation:
Leaderboard leaderboard = new Leaderboard ();
leaderboard.addScore(1,73);   // leaderboard = [[1,73]];
leaderboard.addScore(2,56);   // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39);   // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51);   // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4);    // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1);           // returns 73;
leaderboard.reset(1);         // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2);         // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51);   // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3);           // returns 141 = 51 + 51 + 39;

Constraints:

1 <= playerId, K <= 10000
It’s guaranteed that K is less than or equal to the current number of players.
1 <= score <= 100
There will be at most 1000 function calls.

Solution

Method 1 – Hash Map and Sorting for Top K

Intuition

We need to efficiently update player scores, get the sum of top K scores, and reset scores. A hash map allows fast updates and lookups, and sorting the values allows us to get the top K scores easily (acceptable for up to 1000 calls and 10,000 players).

Approach

Use a hash map to store playerId to score mapping.
For addScore, add the score to the player’s current score (or set if new).
For top(K), get all scores, sort them in descending order, and sum the top K.
For reset, remove the player from the map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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:
        if playerId in self.scores:
            del self.scores[playerId]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


import java.util.*;
public class Leaderboard {
    private Map<Integer, Integer> scores = new HashMap<>();
    public void addScore(int playerId, int score) {
        scores.put(playerId, scores.getOrDefault(playerId, 0) + score);
    }
    public int top(int K) {
        List<Integer> vals = new ArrayList<>(scores.values());
        vals.sort(Collections.reverseOrder());
        int ans = 0;
        for (int i = 0; i < K; i++) ans += vals.get(i);
        return ans;
    }
    public void reset(int playerId) {
        scores.remove(playerId);
    }
}

Complexity

⏰ Time complexity: O(n log n) for top(K), where n is the number of players, due to sorting. O(1) for addScore and reset.
🧺 Space complexity: O(n), for storing player scores.

Problem#

Examples#

Solution#

Method 1 – Hash Map and Sorting for Top K#

Intuition#

Approach#

Code#

Complexity#