High Five - Leetcode Solution

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.

1