# 1244. Design A Leaderboard

{% embed url="<https://leetcode.com/problems/design-a-leaderboard/>" %}

`addScore` 和`reset` 都很好解决，主要是处理`top(K)` 的问题，找一个无序 array 排序后的前 K 个元素：

1. 可以用`quick select` 来固定第K个元素的位置，然后它前面的就都是比它小/大的。
2. 维护一个长度K的最大堆`max heap`。

原题要会员，最后附一下题目。

{% tabs %}
{% tab title="max heap" %}

```python
class Leaderboard:

    def __init__(self):
        self.scores = defaultdict(int)
        
    # O(1)
    def addScore(self, playerId: int, score: int) -> None:
        self.scores[playerId] += score
        
    # O(logN+log(N-K)).
    def top(self, K: int) -> int:
        heap = []
        for score in self.scores.values():
            if len(heap) < K:
                heapq.heappush(heap, score)
            else:
                heapq.heappushpop(heap, score)
        return sum(heap)
    
    # O(1)
    def reset(self, playerId: int) -> None:
        if playerId in self.scores:
            self.scores.pop(playerId)


# Your Leaderboard object will be instantiated and called as such:
# obj = Leaderboard()
# obj.addScore(playerId,score)
# param_2 = obj.top(K)
# obj.reset(playerId)
```

{% endtab %}

{% tab title="quick select" %}

```python
class Leaderboard:
    def __init__(self):
        self.scores = defaultdict(int)
        
    # O(1)
    def addScore(self, playerId: int, score: int) -> None:
        self.scores[playerId] += score
        
    # Average time complexity should be O(N). Worst-case is O(N^2).
    def top(self, K: int) -> int:
        unsorted = list(self.scores.values()) # Have to make this a list, otherwise Python throws an exception saying we can index dict_values.
        self.quickSelect(unsorted, K - 1, 0, len(unsorted) - 1)
        
        return sum(unsorted[:K])
    
    # Use QuickSelect but sort in reverse order. 
    # We did just for no reason other than it simplifies the code in the return statement of top().
    def quickSelect(self, arr, K, p, q):
        partitionIndex = self.partition(arr, p, q)
        if partitionIndex == K:
            return None
        elif partitionIndex > K:
            # Going left.
            self.quickSelect(arr, K, p, partitionIndex - 1)
        else:
            # Going right.
            self.quickSelect(arr, K, partitionIndex + 1, q)
    
    def partition(self, arr, l, r):
        pivot = arr[r] # choose the last element as the pivot
        i = l
        for j in range(l, r):
            if arr[j] >= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[r] = arr[r], arr[i]
        return i
    
    # O(1)
    def reset(self, playerId: int) -> None:
        if playerId in self.scores:
            del self.scores[playerId]
```

{% endtab %}
{% endtabs %}

### 原题

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;
```
