1244. Design A Leaderboard

Design a Leaderboard class, which has 3 functions:

  1. 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.
  2. top(K): Return the score sum of the top K players.
  3. 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.

 

Example 1:

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.

Rust Solution

use std::collections::BTreeMap;
use std::collections::HashMap;

#[derive(Default, Debug)]
struct Leaderboard {
    players: HashMap<i32, i32>,
    scores: BTreeMap<i32, usize>,
}

impl Leaderboard {
    fn new() -> Self {
        Leaderboard::default()
    }

    fn add_score(&mut self, player_id: i32, score: i32) {
        let player_score = self.players.entry(player_id).or_default();
        if *player_score != 0 {
            let count = self.scores.entry(*player_score).or_default();
            *count -= 1;
            if *count == 0 {
                self.scores.remove(player_score);
            }
        }
        *player_score += score;
        *self.scores.entry(*player_score).or_default() += 1;
    }

    fn top(&mut self, mut k: i32) -> i32 {
        let mut sum = 0;
        for (s, &v) in self.scores.iter().rev() {
            for _ in 0..v {
                sum += s;
                k -= 1;
                if k == 0 {
                    return sum;
                }
            }
        }
        0
    }

    fn reset(&mut self, player_id: i32) {
        let player_score = self.players.entry(player_id).or_default();
        let count = self.scores.entry(*player_score).or_default();
        *count -= 1;
        if *count == 0 {
            self.scores.remove(player_score);
        }
        *player_score = 0;
    }
}

#[test]
fn test() {
    let mut obj = Leaderboard::new();
    obj.add_score(1, 73);
    obj.add_score(2, 56);
    obj.add_score(3, 39);
    obj.add_score(4, 51);
    obj.add_score(5, 4);
    assert_eq!(obj.top(1), 73);
    obj.reset(1);
    obj.reset(2);
    obj.add_score(2, 51);
    assert_eq!(obj.top(3), 141);
}

Having problems with this solution? Click here to submit an issue on github.