Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.
Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj 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 <= 1000items[i].length == 21 <= IDi <= 10000 <= scorei <= 100IDi, there will be at least five scores.Problem Overview: You receive a list of [studentId, score] pairs. Each student may appear multiple times. The task is to compute the average of that student’s top five scores and return the result sorted by student ID.
Approach 1: Group + Sort Scores (O(n log n) time, O(n) space)
Store scores for each student using a hash table. Iterate through the input and append scores to the corresponding list. After grouping, sort each student's score list in descending order using sorting, take the first five values, and compute the integer average. Finally, output results sorted by student ID. This approach is simple and easy to reason about but wastes work because it sorts every score even though only the top five matter.
Approach 2: Hash Map + Min Heap (O(n log 5) time, O(n) space)
Maintain a hash map from student ID to a fixed-size min heap (priority queue). For each incoming score, push it into that student's heap. If the heap grows larger than five elements, remove the smallest score. The heap always stores the student's top five scores because smaller ones get discarded. After processing all entries, sum the heap values and divide by five to compute the average. Heap operations take O(log 5), which is effectively constant, making the overall complexity O(n). This avoids sorting entire score lists.
Approach 3: Sort by Student and Score (O(n log n) time, O(1) extra space excluding output)
Sort the input array by studentId ascending and score descending. Then scan the sorted list and accumulate the first five scores you encounter for each student. Because the highest scores appear first, you can stop counting once five scores are collected and ignore the rest. This method keeps logic simple but still pays the full O(n log n) sorting cost.
Recommended for interviews: The hash map + min heap approach is typically expected. It shows that you recognize only the top five scores matter and avoids unnecessary sorting. Mentioning the group-and-sort solution first demonstrates baseline problem solving, but implementing the heap optimization shows stronger command of data structures and complexity tradeoffs.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Group Scores + Sort | O(n log n) | O(n) | Simplest implementation when performance is not critical |
| Hash Map + Min Heap (Top 5) | O(n log 5) ≈ O(n) | O(n) | Optimal approach when you only need the top k elements |
| Sort by ID and Score | O(n log n) | O(1) extra | Useful if sorting is already required for other processing |
LeetCode 1086: High Five - Interview Prep Ep 11 • Fisher Coder • 6,676 views views
Watch 9 more video solutions →Practice High Five with our built-in code editor and test cases.
Practice on FleetCode