Skip to content

1244. Design A Leaderboard 👍

  • Time:
    • Constructor: $O(1)$
    • addScore(playerId: int, score: int): $O(1)$
    • top(K: int): $O(n\log k)$
    • reset(playerId: int): $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Leaderboard {
 public:
  void addScore(int playerId, int score) {
    idToScore[playerId] += score;
  }

  int top(int K) {
    int ans = 0;
    priority_queue<int, vector<int>, greater<>> minHeap;

    for (const auto& [id, score] : idToScore) {
      minHeap.push(score);
      if (minHeap.size() > K)
        minHeap.pop();
    }

    while (!minHeap.empty())
      ans += minHeap.top(), minHeap.pop();

    return ans;
  }

  void reset(int playerId) {
    idToScore.erase(playerId);
  }

 private:
  unordered_map<int, int> idToScore;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Leaderboard {
  public void addScore(int playerId, int score) {
    idToScore.merge(playerId, score, Integer::sum);
  }

  public int top(int K) {
    int ans = 0;
    Queue<Integer> minHeap = new PriorityQueue<>();

    for (final int score : idToScore.values()) {
      minHeap.offer(score);
      if (minHeap.size() > K)
        minHeap.poll();
    }

    while (!minHeap.isEmpty())
      ans += minHeap.poll();

    return ans;
  }

  public void reset(int playerId) {
    idToScore.remove(playerId);
  }

  private Map<Integer, Integer> idToScore = new HashMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Leaderboard:
  def __init__(self):
    self.idToScore = collections.Counter()

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

  def top(self, K: int) -> int:
    return sum(score for _, score in self.idToScore.most_common(K))

  def reset(self, playerId: int) -> None:
    del self.idToScore[playerId]