Leetcode 1244. Design A Leaderboard

Problem Explanation: You need to design a leaderboard class that has 3 methods:

• "addScore": This method takes into account the integer id of a player and their score, and updates the leaderboard by either adding the player (if they're not already in the leaderboard) with the given score, or updating the current player's score by adding to it.
• "top": This method calculates the sum of scores of the top 'k' players.
• "reset": This method resets a player's score to zero, if their id is provided.

Approach: To solve this problem, we can use a hashmap. The hashmap will map each player's id to their respective score. This way, we can easily update a player's score or reset it. For calculating top 'k' scores, we can use a minHeap.

Let's consider an example to illustrate this:

1
2cpp
3  []. addScore(1, 73) -> adds player 1 to leaderboard -> {1:73}
4  addScore(2, 56)    -> adds player 2 to leaderboard -> {1:73, 2:56}
5  addScore(3, 39)    -> adds player 3 to leaderboard -> {1:73, 2:56, 3:39}
6  top(1)            -> gets scores of top 1 player   -> {1:73} -> returns 73
7  reset(2)          -> resets player 2's score       -> {1:73, 3:39}
8  addScore(2, 51)   -> adds player 2 back to leaderboard -> {1:73, 2:51, 3:39}
9  top(3)            -> gets scores of top 3 players  -> {1:73, 2:51, 3:39} -> returns 163

Here, we perform the operations in the sequence they occur and update our hashmap.

Let's see how to implement this in different languages

Python Solution:

1
2python
3import heapq
4
5class Leaderboard:
6
7    def __init__(self):
8        self.score = {}
9
10    def addScore(self, playerId: int, score: int) -> None:
11        if playerId not in self.score:
12            self.score[playerId] = score
13        else:
14            self.score[playerId] += score
15
16    def top(self, K: int) -> int:
17        return sum(heapq.nlargest(K, self.score.values()))
18
19    def reset(self, playerId: int) -> None:
20        del self.score[playerId]

Here, heapq is a Python module which implements a heap queue algorithm, also known as priority queue algorithm.

Java Solution:

1
2java
3class Leaderboard {
4    Map<Integer, Integer> scores;
5    public Leaderboard() {
6        scores = new HashMap<>();
7    }
8    
9    public void addScore(int playerId, int score) {
10       scores.put(playerId, scores.getOrDefault(playerId, 0) + score);   
11    }
12    
13    public int top(int K) {
14        return scores.values().stream().sorted(Collections.reverseOrder()).limit(K).reduce(0, Integer::sum);
15    }
16    
17    public void reset(int playerId) {
18        scores.put(playerId, 0);
19    }
20}

In Java, we use a HashMap to store the player id and their score as key-value pairs.

JavaScript Solution:

1
2javascript
3class Leaderboard {
4    constructor() {
5        this.scores = new Map();
6    }
7  
8    addScore(playerId, score) {
9        this.scores.set(playerId, (this.scores.get(playerId) || 0) + score);
10    }
11  
12    top(K) {
13        return Array.from(this.scores.values()).sort((a, b) => b - a).slice(0, K).reduce((a, b) => a + b, 0);
14    }
15  
16    reset(playerId) {
17        this.scores.delete(playerId);
18    }
19}

In JavaScript, we use the Map object which holds key-value pairs.

C++ Solution:

1
2cpp
3class Leaderboard {
4 public:
5  void addScore(int playerId, int score) {
6    idToScore[playerId] += score;
7  }
8
9  int top(int K) {
10    int sum = 0;
11    priority_queue<int, vector<int>, greater<>> minHeap;
12
13    for (const auto& [id, score] : idToScore) {
14      minHeap.push(score);
15      if (minHeap.size() > K)
16        minHeap.pop();
17    }
18
19    while (!minHeap.empty())
20      sum += minHeap.top(), minHeap.pop();
21
22    return sum;
23  }
24
25  void reset(int playerId) {
26    idToScore.erase(playerId);
27  }
28
29 private:
30  unordered_map<int, int> idToScore;
31};

In the C++ solution, we have made use of an unordered_map to keep track of scores.

C# Solution:

1
2csharp
3public class Leaderboard {
4    Dictionary<int, int> scores;
5
6    public Leaderboard() {
7        scores = new Dictionary<int, int>();
8    }
9    
10    public void AddScore(int playerId, int score) {
11        if(scores.ContainsKey(playerId))
12            scores[playerId] += score;
13        else
14            scores[playerId] = score;
15    }
16
17    public int Top(int K) {
18        return scores.Values.OrderByDescending(i => i).Take(K).Sum();
19    }
20
21    public void Reset(int playerId) {
22        scores[playerId] = 0;
23    }
24}

In the C# solution, we use a Dictionary object to keep track of player scores.Ruby Solution:

1
2ruby
3class Leaderboard
4  attr_reader :scores
5
6  def initialize
7    @scores = Hash.new(0)
8  end
9
10  def add_score(player_id, score)
11    scores[player_id] += score
12  end
13
14  def top(k)
15    scores.values.sort.reverse.take(k).inject(0, :+)
16  end
17
18  def reset(player_id)
19    scores.delete(player_id)
20  end
21end

In this Ruby solution, we make use of Hash for storing scores. The built-in methods sort, reverse, and take are conveniently used to retrieve the top k scores.

Swift Solution:

1
2swift
3class Leaderboard {
4    var scores: [Int: Int] = [:]
5
6    func addScore(_ playerId: Int, _ score: Int) {
7        if let _ = scores[playerId] {
8            scores[playerId]! += score
9        } else {
10            scores[playerId] = score
11        }
12    }
13
14    func top(_ K: Int) -> Int {
15        return Array(scores.values).sorted { $0 > $1 }.prefix(K).reduce(0, +)
16    }
17
18    func reset(_ playerId: Int) {
19        scores[playerId] = 0
20    }
21}

For Swift, we use a Dictionary to store the player's scores. The sorted method can get the top k scores. The prefix method is used to select the first K elements from the sorted array. The reduce method then cumulatively combines these elements using the addition operator.

Rust Solution:

1
2rust
3use std::collections::HashMap;
4
5struct Leaderboard {
6    scores: HashMap<i32, i32>,
7}
8
9impl Leaderboard {
10    fn new() -> Self {
11        Self {
12            scores: HashMap::new(),
13        }
14    }
15
16    fn add_score(&mut self, player_id: i32, score: i32) {
17        let current_score = self.scores.entry(player_id).or_insert(0);
18        *current_score += score;
19    }
20
21    fn top(&self, k: usize) -> i32 {
22        let mut scores: Vec<&i32> = self.scores.values().collect();
23        scores.sort_unstable();
24        scores.iter().rev().take(k).sum::<&i32>().clone()
25    }
26
27    fn reset(&mut self, player_id: i32) {
28        self.scores.remove(&player_id);
29    }
30}

In Rust, we present a mutable hashmap to record the score of each player. The entry method of a mutable hashmap returns a mutable reference pointing to the value corresponding to the key. The or_insert method can insert a default value when the key is not existed yet in the hashmap. The remove method will eliminate the player from the leaderboard.

In conclusion, the above solutions effectively implement the leaderboard class using different programming languages. The hashmap provides constant-time performance for score add and reset operations, while heap or sorted array provides a relatively efficient manner to retrieve top k scores.