Problem Description

The Design A Leaderboard problem on LeetCode asks you to implement a simple leaderboard system that supports the following operations:

• addScore(playerId, score): Add score points to the player's total score. If the player does not exist, create a new entry for them.
• top(K): Return the sum of the top K highest scores among all players.
• reset(playerId): Reset the score of the player with playerId back to 0.

• Each playerId is unique.
• Scores can be positive or negative integers.
• Multiple operations will be called in any order.
• Efficient performance is important: avoid brute-force recalculation for each top(K) call.

Thought Process

At first, you might think of storing each player's score in a simple dictionary or map. This makes addScore and reset easy, but top(K) would require sorting all scores every time it's called, which is inefficient for large numbers of players or frequent queries.

To optimize, we want a way to quickly get the top K scores without sorting the entire list every time. This suggests using a data structure that maintains order, such as a heap or a balanced binary search tree. However, since we only need the top K scores (not the full ranking), we can use a min-heap of size K or simply sort the values when top(K) is called, as long as the number of players is not too large.

The main challenge is balancing efficient updates (addScore, reset) with efficient queries (top(K)).

Solution Approach

Let's break down the design step by step:

1. Data Storage:
   • Use a hash map (dictionary) to store each playerId and their current score. This gives O(1) add, update, and reset operations.
2. addScore(playerId, score):
   • If playerId exists, add score to the current total. Otherwise, create a new entry with the score.
3. reset(playerId):
   • Set the player's score to 0. (Or remove them entirely, depending on the requirements. Here, we set to 0.)
4. top(K):
   • Get all current scores from the hash map.
   • Find the top K scores. There are two common ways:
     • Sort the list of scores in descending order and sum the first K elements (simple and works well for small to moderate N).
     • Use a min-heap of size K to keep track of the largest K scores (more efficient for very large N).

Example Walkthrough

Let's walk through a sample sequence of operations:
addScore(1, 73)
addScore(2, 56)
addScore(3, 39)
addScore(4, 51)
addScore(5, 4)
top(1) // returns 73
reset(1)
reset(2)
addScore(2, 51)
top(3) // returns 141 (51 + 51 + 39)

Step-by-step:

• After all adds: player scores = {1:73, 2:56, 3:39, 4:51, 5:4}
• top(1): Highest score is 73 (player 1)
• reset(1): player 1 score becomes 0
• reset(2): player 2 score becomes 0
• addScore(2, 51): player 2 score becomes 51
• Current scores: {1:0, 2:51, 3:39, 4:51, 5:4}
• top(3): Top 3 scores are 51 (player 2), 51 (player 4), 39 (player 3) → sum is 141

Time and Space Complexity

Brute-force Approach:

• addScore and reset: O(1) each (just a dictionary update)
• top(K): O(N log N) because we sort all scores every time, where N is the number of players

• addScore and reset: O(1)
• top(K): O(N log K) using a min-heap of size K

• O(N) for storing the player scores in the hash map.

Summary

The Leaderboard problem is a classic example of balancing fast updates with fast queries. By using a hash map for constant-time updates and either sorting or a min-heap for efficient top-K queries, we can support all operations efficiently. The main insight is recognizing that while addScore and reset are straightforward, top(K) requires careful consideration to avoid unnecessary sorting or scanning of all data. This design demonstrates the power of combining simple data structures for flexible and performant solutions.

Code Implementation

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

    def addScore(self, playerId: int, score: int) -> None:
        if playerId in self.scores:
            self.scores[playerId] += score
        else:
            self.scores[playerId] = score

    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
      

class Leaderboard {
public:
    unordered_map<int, int> scores;

    Leaderboard() {}

    void addScore(int playerId, int score) {
        scores[playerId] += score;
    }

    int top(int K) {
        vector<int> vals;
        for (auto &p : scores)
            vals.push_back(p.second);
        sort(vals.rbegin(), vals.rend());
        int sum = 0;
        for (int i = 0; i < K && i < vals.size(); ++i)
            sum += vals[i];
        return sum;
    }

    void reset(int playerId) {
        scores[playerId] = 0;
    }
};
      

import java.util.*;

class Leaderboard {
    private Map<Integer, Integer> scores;

    public Leaderboard() {
        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 sum = 0;
        for (int i = 0; i < K && i < vals.size(); i++)
            sum += vals.get(i);
        return sum;
    }

    public void reset(int playerId) {
        scores.put(playerId, 0);
    }
}
      

class Leaderboard {
    constructor() {
        this.scores = new Map();
    }

    addScore(playerId, score) {
        this.scores.set(playerId, (this.scores.get(playerId) || 0) + score);
    }

    top(K) {
        let vals = Array.from(this.scores.values());
        vals.sort((a, b) => b - a);
        return vals.slice(0, K).reduce((a, b) => a + b, 0);
    }

    reset(playerId) {
        this.scores.set(playerId, 0);
    }
}