Solution: High Five

Statement

You are given a list of scores for multiple students, represented as items, where $items[i] = [ID_i, score_i]$ indicates the ID of a student $(ID_i)$ and their score $(score_i)$. Your task is to compute the top five average scores for each student.

Return the result as an array of pairs, result, where $result[j] = [ID_j, topFiveAverage_j]$ represents the student with ID, $ID_j$, and their corresponding top five average scores. The result should be sorted in ascending order by $ID_j$.

Note: To calculate the top five averages for each student, sum their highest five scores and perform integer division by $5$.

Constraints:

• $1 <=$ items.length $<= 1000$

• items[i].length $== 2$

• $1 <= ID_i <= 1000$

• $0 <= score_i <= 100$

• For each $ID_i$, there will be at least five scores.

Solution

The idea is to use a hash map (dictionary) to store the scores for each student and then calculate the average of the top five scores for each student using sorting. The approach keeps track of the scores by using a dictionary where each key represents a student ID, and the corresponding value is a list of scores for that student. The solution sorts the scores for each student to find the top five, ensuring an accurate average calculation.

Now, let’s walk-through the steps of the solution:

1. We create a dictionary, dict, to store scores for each student ID.

2. We create a variable max_id, to keep track of the highest student ID encountered.

3. We iterate through the items list, where each element is a pair $[ID, score]$ of a student, and for each pair:

   1. We append the $score$ corresponding to the ID in dict.

   2. We update max_id  to the $maximum(current ID,$ max_id$)$. We do this to keep track of the highest student ID seen.

4. After iterating through items and storing scores in dict, we initialize an empty list result to store the final output.

5. Next, we iterate through all possible IDs from 1 to max_id (inclusive) and check whether there are scores in dict for each ID. If there are, we do the following:

   1. We find the top $5$ scores for the current student.

   2. We calculate the average of the top $5$ scores using integer division.

   3. We append the pair $[ID, AverageScore]$ to the result list.

6. Finally, we return result, which contains each student's ID and their corresponding top five average scores.

Let’s look at the following illustration to get a better understanding of the solution: