1244. Design A Leaderboard

MediumDesignHash TableSorting

Problem Description

The goal is to design a Leaderboard class that can perform three operations on the scores of players:

addScore(playerId, score): This updates the leaderboard by adding the specified score to a player's overall score, identified by playerId. If a player does not exist on the leaderboard, they are added with the initial score.
top(K): This operation calculates the sum of scores of the top K players on the leaderboard. The top players are the ones with the highest scores.
reset(playerId): This resets a player's score to 0, effectively erasing their score from the leaderboard. It is a pre-condition that the player was previously added to the leaderboard before this function is called.

The leaderboard is initially empty and becomes populated as players are added with their scores.

Intuition

To solve this problem, we need to efficiently keep track of the scores of players and be able to quickly perform operations like adding new scores, retrieving the top scores, and resetting scores for specific players. The key challenges here are ensuring quick updates to scores and fast retrieval for the top K scores.

The solution uses two data structures:

A defaultdict(int) from the collection's module, which provides default values for missing keys and is used here to store player scores. It maps player IDs to their scores.
A SortedList from the sortedcontainers library, which maintains a sorted list of scores. This allows efficient insertion, removal, and access to the largest scores in order to compute the sum of the top K scores.

For the addScore method, we first check if the player ID is already in the dictionary. If it isn't, we add the player ID and the score to the dictionary and the score to the SortedList. If the player ID exists, we remove the old score, update the score in the dictionary, and re-insert the new score into the SortedList.

The top(K) method is straightforward with the SortedList because we can directly access the last K elements (which are the largest due to the sorted property of the list) and return their sum.

The reset method removes the player's score by popping the player ID from the dictionary and also removing the associated score from the SortedList.

The intuition behind using SortedList is that it takes advantage of the fact that scores need to be sorted for the top(K) method. Although it incurs some cost when adding and resetting scores due to re-sorting, it is balanced out by the efficient retrieval of the top K scores, which can be expected to be a frequent operation in this context.

Learn more about Sorting patterns.

Solution Approach

The solution for the Leaderboard problem involves using both a hashmap and a sorted list to efficiently manage players' scores and sort them when necessary. Here's a detailed walk-through of the implementation:

Data Structures Used

defaultdict(int): The choice of defaultdict for storing player scores is to ensure that if we try to access or update a player's score that isn't in the dictionary yet, it will by default be initialized to 0.
SortedList: The SortedList is used to maintain the scores in a sorted order. This sorted data structure provides us with the means to quickly access the highest scores needed for the top(K) method.

Algorithmic Steps

`init` method

The constructor initializes the defaultdict self.d for player scores and the self.rank which is a SortedList to maintain the ordered scores.

`addScore` method

Check if playerId exists in the dictionary self.d:
- If it does not exist, add playerId with the given score to the dictionary and also add this score to the SortedList (self.rank.add(score)).
- If it does exist, we must first remove the old score from SortedList, update the dictionary with the new score, and then add the updated score back into the SortedList.
Doing this ensures the SortedList always contains the current scores of all players in sorted order, allowing efficient computation of the top scores.

`top` method

Simply access the last K scores from the sorted list using slicing (self.rank[-K:]) and return their sum (sum(self.rank[-K:])).
Since SortedList maintains the scores in ascending order, the last K elements represent the K highest scores.

`reset` method

This involves two steps:
- First, remove the player's score from the SortedList (self.rank.remove(self.d[playerId])).
- Then, remove the player's score from the dictionary (self.d.pop(playerId)).
This operation effectively sets the player's score to zero and removes them from the tracking in SortedList.

Time Complexity

The time complexity for addScore and reset is O(log N) where N is the number of unique player IDs, as these operations involve adding/removing elements to/from the SortedList, which is done in logarithmic time. The top(K) operation has a time complexity of O(K), which is required to compute the sum of the top K elements.

By balancing the operations with appropriate data structures — defaultdict for direct access and modifications, and SortedList for maintaining order — we ensure that all the required operations can be performed efficiently for the Leaderboard class.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example with imaginary player IDs and scores to illustrate how the Leaderboard class handles the operations based on the solution approach described.

Initializing the Leaderboard

We start by creating an instance of the Leaderboard class. This initializes an empty defaultdict for player scores and an empty SortedList for maintaining the scores in sorted order.

Adding Scores

Suppose we call addScore(1, 50).
- Since player ID 1 is not in the defaultdict, we add this player with a score of 50 to the dictionary and the SortedList.
Now, we call addScore(2, 80).
- Player ID 2 isn't in the dictionary either, so we perform the same steps as we did with player ID 1.
Then we call addScore(1, 30).
- This time player ID 1 already exists in the dictionary. Its score is now 50 + 30 = 80. We need to update the SortedList by removing the old score and inserting the new combined score.

Our SortedList currently has two scores: [80, 80] (both for player ID 1 and player ID 2).

Retrieving Top Scores

We make a call to top(1).
- We want the sum of the top 1 player's score, which is just the highest score. Since our SortedList is in ascending order, we look at the last element which is 80. The result of top(1) is therefore 80.

Resetting a Player's Score

Assume we want to reset the score for player ID 1 by calling reset(1).
- We find the score for player ID 1 in the defaultdict, which is 80, and remove it from the SortedList.
- Then we set player ID 1's score back to 0 in the defaultdict. However, since zero scores are not kept in the SortedList, we effectively just remove the score.

If we were now to call top(1) again, the highest score in the SortedList would be 80, which belongs to player ID 2 since player ID 1's score has been reset.

By going through this example, it demonstrates the efficiency of the data structures chosen for the Leaderboard class in handling updates, queries, and resets. The defaultdict provides quick updates and access to player scores while the SortedList ensures the top(K) operation is fast by keeping scores in a sorted state, allowing quick retrieval of the largest scores.

Solution Implementation

1from sortedcontainers import SortedList
2from collections import defaultdict
3
4class Leaderboard:
5    def __init__(self):
6        # A mapping from player ID to their score
7        self.scores_by_player = defaultdict(int)
8        # A sorted list of scores for efficient ranking
9        self.sorted_scores = SortedList()
10
11    def addScore(self, playerId: int, score: int) -> None:
12        """
13        Add score to a player. If the player does not exist, create their record. 
14        Otherwise, update their score and maintain the sorted order of scores.
15        """
16        if playerId not in self.scores_by_player:
17            self.scores_by_player[playerId] = score
18            self.sorted_scores.add(score)  # Player is new, add score directly
19        else:
20            # Player exists, remove the old score
21            self.sorted_scores.remove(self.scores_by_player[playerId])
22            # Update the player's score
23            self.scores_by_player[playerId] += score
24            # Add the updated score for the player
25            self.sorted_scores.add(self.scores_by_player[playerId])
26
27    def top(self, K: int) -> int:
28        """
29        Calculate the sum of the top K players' scores.
30        """
31        # Since the sorted_scores list is in ascending order, get the last K scores for top players
32        return sum(self.sorted_scores[-K:])
33
34    def reset(self, playerId: int) -> None:
35        """
36        Reset a player's score by removing it from the sorted list and player dictionary.
37        """
38        # Remove the player's score from the sorted list
39        self.sorted_scores.remove(self.scores_by_player[playerId])
40        # Remove the player's score from the dictionary
41        del self.scores_by_player[playerId]
42
43# Usage Example
44# Create a Leaderboard instance.
45# leaderboard = Leaderboard()
46# Add score for a player.
47# leaderboard.addScore(playerId, score)
48# Retrieve the sum of the top K players' scores.
49# top_scores = leaderboard.top(K)
50# Reset a player's score.
51# leaderboard.reset(playerId)
52

1import java.util.HashMap;
2import java.util.Map;
3import java.util.TreeMap;
4
5/**
6 * The Leaderboard class keeps track of scores of players in a game,
7 * providing functions to add scores, retrieve the top scores, and reset a player's score.
8 */
9class Leaderboard {
10    // A HashMap to store the playerId and their corresponding scores. 
11    private Map<Integer, Integer> playerScores = new HashMap<>();
12
13    // A TreeMap to maintain sorted scores (in descending order) along with their frequency.
14    private TreeMap<Integer, Integer> sortedScores = new TreeMap<>((a, b) -> b - a);
15
16    /**
17     * Constructor not needed as there is no initialization required
18     * beyond the instance variables already being declared.
19     */
20    public Leaderboard() {
21    }
22
23    /**
24     * Adds score to the playerId's current score.
25     * If the playerId does not exist, they are added to the Leaderboard.
26     *
27     * @param playerId Identifier for the player.
28     * @param score Score to add to the player's existing score.
29     */
30    public void addScore(int playerId, int score) {
31        // Merge the new score into the existing one or put if absent, then get the updated score
32        playerScores.merge(playerId, score, Integer::sum);
33        int updatedScore = playerScores.get(playerId);
34
35        // If the score is an update (not the first score), reduce the frequency of the old score
36        if (updatedScore != score) {
37            sortedScores.merge(updatedScore - score, -1, Integer::sum);
38        }
39
40        // Add or update the frequency of the new score
41        sortedScores.merge(updatedScore, 1, Integer::sum);
42    }
43
44    /**
45     * Retrieves the sum of top K scores.
46     *
47     * @param K The number of top scores to accumulate.
48     * @return The sum of the top K scores.
49     */
50    public int top(int K) {
51        int sum = 0;
52
53        // Iterate over the scores in descending order
54        for (var entry : sortedScores.entrySet()) {
55            int score = entry.getKey();
56            int count = entry.getValue();
57
58            // Take only as many scores as needed to fulfill the quantity K
59            count = Math.min(count, K);
60            sum += score * count;
61            K -= count;
62
63            // If the top K scores are accumulated, we can break early
64            if (K == 0) {
65                break;
66            }
67        }
68        return sum;
69    }
70
71    /**
72     * Resets the score for a given playerId.
73     *
74     * @param playerId The identifier of the player whose score is to be reset.
75     */
76    public void reset(int playerId) {
77        // Remove the player's score
78        int score = playerScores.remove(playerId);
79
80        // Decrement the frequency of the player's score and if it reaches zero, remove it from sortedScores
81        if (sortedScores.merge(score, -1, Integer::sum) == 0) {
82            sortedScores.remove(score);
83        }
84    }
85}
86
87// The Leaderboard class usage example (this comment block could be removed)
88/*
89Leaderboard leaderboard = new Leaderboard();
90leaderboard.addScore(playerId, score); // Add score for a player
91int topScores = leaderboard.top(K);    // Retrieve the sum of top K scores
92leaderboard.reset(playerId);           // Reset the score of a player
93*/
94

1#include <unordered_map>
2#include <set>
3#include <functional>
4
5// The Leaderboard class is designed to track the score of each player and provide leaderboards.
6class Leaderboard {
7public:
8    // Constructor with no initialization needed as C++ members initialize by themselves.
9    Leaderboard() {
10    }
11
12    // Add score to the player's current score. If the player doesn't exist, create a new entry.
13    void addScore(int playerId, int score) {
14        playerScores[playerId] += score; // Update the score for the given player.
15        int newScore = playerScores[playerId];
16      
17        // If the player existed before (this is not their first score),
18        // remove the old score from the ranking set.
19        if (newScore != score) {
20            scoresRanking.erase(scoresRanking.find(newScore - score));
21        }
22        scoresRanking.insert(newScore); // Insert the new score into the ranking set.
23    }
24
25    // Return the sum of the top K scores.
26    int top(int K) {
27        int sum = 0; // Initialize the sum of top K scores to zero.
28      
29        // Iterate over the sorted set of scores to accumulate the top K scores.
30        for (auto score : scoresRanking) {
31            sum += score;
32            if (--K == 0) {
33                // If K reaches zero, we have added enough scores to the sum.
34                break;
35            }
36        }
37        return sum; // Return the sum of the top K scores.
38    }
39
40    // Reset a player's score to zero by removing them from the map and set.
41    void reset(int playerId) {
42        int score = playerScores[playerId]; // Get the current score of the player.
43        playerScores.erase(playerId); // Remove player's score from the playerScores map.
44        scoresRanking.erase(scoresRanking.find(score)); // Remove player's score from the scoresRanking set.
45    }
46
47private:
48    // Map to store player ID and their corresponding scores.
49    std::unordered_map<int, int> playerScores;
50    // Multiset to store scores in descending order for easy ranking.
51    std::multiset<int, std::greater<int>> scoresRanking;
52};
53
54// Usage example:
55// Leaderboard* leaderboard = new Leaderboard();
56// leaderboard->addScore(playerId, score);
57// int topScoresSum = leaderboard->top(K);
58// leaderboard->reset(playerId);
59// delete leaderboard;
60

1// Store player ID and their corresponding scores in a map.
2const playerScores: Record<number, number> = {};
3
4// Multiset equivalent: using a map to store scores and their occurrences in sorted order.
5const scoresRanking: Map<number, number> = new Map();
6
7// Add score to the player's current score. If the player doesn't exist, create a new entry.
8function addScore(playerId: number, score: number): void {
9  const currentScore = playerScores[playerId] || 0;
10  const newScore = currentScore + score;
11  playerScores[playerId] = newScore; // Update the score for the given player.
12
13  // If the player already had a score, decrement the occurrence of the old score.
14  if (currentScore !== 0) {
15    const count = scoresRanking.get(currentScore) || 0;
16    if (count - 1 === 0) {
17      scoresRanking.delete(currentScore);
18    } else {
19      scoresRanking.set(currentScore, count - 1);
20    }
21  }
22
23  // Add the new score to the ranking set, increment the occurrence.
24  const newScoreCount = scoresRanking.get(newScore) || 0;
25  scoresRanking.set(newScore, newScoreCount + 1);
26}
27
28// Return the sum of the top K scores.
29function top(K: number): number {
30  let sum = 0; // Initialize the sum of top K scores to zero.
31  const sortedScores = Array.from(scoresRanking.keys()).sort((a, b) => b - a);
32
33  // Iterate over the sorted scores to accumulate the top K scores.
34  for (const score of sortedScores) {
35    let count = scoresRanking.get(score) || 0;
36    while (count > 0 && K > 0) {
37      sum += score;
38      count--;
39      K--;
40    }
41
42    if (K === 0) break;
43  }
44
45  return sum; // Return the sum of the top K scores.
46}
47
48// Reset a player's score to zero by removing their score from the playerScores map and scoresRanking set.
49function reset(playerId: number): void {
50  const score = playerScores[playerId]; // Get the current score of the player.
51  delete playerScores[playerId]; // Remove player's score from the playerScores map.
52
53  // Remove the player's score from the scoresRanking multiset equivalent.
54  const count = scoresRanking.get(score) || 0;
55  if (count - 1 === 0) {
56    scoresRanking.delete(score);
57  } else {
58    scoresRanking.set(score, count - 1);
59  }
60}
61
62// Example usage:
63// addScore(playerId, score);
64// const topScoresSum = top(K);
65// reset(playerId);
66

Time and Space Complexity

Constructor - __init__(self):

Time Complexity: O(1) for initializing the dictionary and the sorted list.
Space Complexity: O(N) since space is allocated for the dictionary self.d and the sorted list self.rank, where N is the number of different playerIds.

Add Score - addScore(self, playerId: int, score: int):

Time Complexity: If playerId is not in self.d, then it is O(log N) for adding score to the sorted list. If playerId is in self.d, it is O(log N) for removing the existing score and O(log N) for adding the new score, so overall is O(log N).
Space Complexity: Since we are only updating the dictionary and the sorted list with integers, space complexity remains O(N) (no additional space proportional to the input size is used in this operation).

Top - top(self, K: int):

Time Complexity: O(K) for summing the top K scores since it retrieves the last K elements of the sorted list which is in O(K).
Space Complexity: O(1) as it returns an integer sum and does not require additional space.

Reset - reset(self, playerId: int):

Time Complexity: O(log N) for removing a score from the sorted list as it needs to search and remove an element.
Space Complexity: O(1) for removing the player's score; the overall space used by the data structures decreases by a constant amount.

Overall:

The space complexity of the Leaderboard class as a whole is O(N), accounting for the space needed to store a score for each player.
The time complexity of each operation is either O(1), O(K), or O(log N), without nested operations that would increase complexity further.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know