## Description

https://leetcode.com/problems/high-five/

Given a list of the scores of different students, `items`

, where `items[i] = [ID`

represents one score from a student with _{i}, score_{i}]`ID`

, calculate each student’s _{i}**top five average**.

Return *the answer as an array of pairs *`result`

*, where *`result[j] = [ID`

_{j}, topFiveAverage_{j}]* represents the student with *`ID`

_{j}* and their top five average. Sort *

`result`

*by*

`ID`_{j}

*in*

**increasing order**.A student’s **top five average** is calculated by taking the sum of their top five scores and dividing it by `5`

using **integer division**.

**Example 1:**

Input:items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]Output:[[1,87],[2,88]]Explanation:The student with ID = 1 got scores 91, 92, 60, 65, 87, and 100. Their top five average is (100 + 92 + 91 + 87 + 65) / 5 = 87. The student with ID = 2 got scores 93, 97, 77, 100, and 76. Their top five average is (100 + 97 + 93 + 77 + 76) / 5 = 88.6, but with integer division their average converts to 88.

**Example 2:**

Input:items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]Output:[[1,100],[7,100]]

**Constraints:**

`1 <= items.length <= 1000`

`items[i].length == 2`

`1 <= ID`

_{i}<= 1000`0 <= score`

_{i}<= 100- For each
`ID`

, there will be_{i}**at least**five scores.

## Explanation

Use a heap to maintain the scores in order.

## Python Solution

```
class Solution:
def highFive(self, items: List[List[int]]) -> List[List[int]]:
scores = defaultdict(list)
for item in items:
heapq.heappush(scores[item[0]], -item[1])
results = []
for key, value in scores.items():
sum = 0
for i in range(5):
sum += -heappop(value)
average = sum // 5
heapq.heappush(results, [key, average])
return results
```

- Time Complexity: O(N logN). Similarly pushing an item in the max heap also takes O(log N). Hence to insert all the N elements, the total time taken is O(N \log N). Iterating over the map takes O(N) time and extracting the top 5 elements is a constant time operation. Hence the overall time taken is O(N log N).
- Space Complexity: O(N).