## Similar Problems

Similar Problems not available

# High Five - Leetcode Solution

## Companies:

LeetCode: High Five Leetcode Solution

Difficulty: Easy

Topics: hash-table sorting heap-priority-queue array

The High Five problem on LeetCode is a problem that involves finding the average of the top five scores of each student. The problem can be solved using a hash map and a priority queue.

The problem statement can be written as follows:

Given a list of scores of different students, return the average score of each student's top five scores in the order of their appearance in the input list. Each entry items[i] has items[i][0] the student's ID, and items[i][1] the student's score. The average score is calculated using integer division.

Example:

Input: [[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 average of the top 5 scores of student 1 is (100 + 92 + 91 + 87 + 65) / 5 = 87.

The average of the top 5 scores of student 2 is (100 + 97 + 93 + 77 + 76) / 5 = 88.

To solve the problem, we can create a hash map to store the scores of each student. The key of the hash map will be the student ID, and the value will be a priority queue containing the scores of the student. The priority queue will be used to keep track of the top five scores of each student.

We can then iterate through the list of scores and add each score to the corresponding priority queue in the hash map. After adding the scores, we can iterate through the hash map and calculate the average of the top five scores of each student.

Here's the implementation of the solution in Python:

def high_five(items):

```
# create a hash map to store the scores of each student
scores = {}
for item in items:
student_id, score = item
if student_id not in scores:
# create a priority queue for the student if not already present
scores[student_id] = []
# add the score to the priority queue
heapq.heappush(scores[student_id], score)
# keep only the top five scores
if len(scores[student_id]) > 5:
heapq.heappop(scores[student_id])
averages = []
for student_id in sorted(scores.keys()):
# calculate the average of the top five scores
average = sum(scores[student_id]) // len(scores[student_id])
averages.append([student_id, average])
return averages
```

The time complexity of the solution is O(n log k), where n is the number of scores and k is the maximum number of scores per student (in this case, k = 5). The space complexity is O(n), as we use a hash map to store the scores of each student.

## High Five Solution Code

`1`