1. Using Sorting

Intuition

We need to find each student's average of their top 5 scores.
If we sort all items by student ID (ascending) and by score (descending), then for each student, their first 5 entries will be their highest scores.
We can then group by student, sum their top 5 scores, and compute the average.

Algorithm

1. Sort the items array by student ID in ascending order. For the same ID, sort by score in descending order.
2. Iterate through the sorted array, processing one student at a time.
3. For each student, sum their first 5 scores (which are the highest due to sorting).
4. Skip any remaining scores for that student.
5. Store the student ID and their average (sum divided by 5) in the result.
6. Return the result array.

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        K = 5
        items.sort(key=lambda x: (x[0], -x[1]))

        solution = []
        n = len(items)
        i = 0
        while i < n:
            id = items[i][0]
            sum_val = 0
            for k in range(i, i + K):
                sum_val += items[k][1]
            while i < n and items[i][0] == id:
                i += 1
            solution.append([id, sum_val // K])

        return solution

Time & Space Complexity

• Time complexity: $O(N \log N)$
• Space complexity: $O(N)$

Where $N$ is the total number of items.

---

2. Using Map and Max Heap

Intuition

Instead of sorting all items, we can use a map to group scores by student ID and a max heap for each student.
The max heap naturally keeps the largest scores at the top, so extracting the top 5 is straightforward.
Using a TreeMap (or sorted map) ensures students are processed in ID order.

Algorithm

1. Create a map where each key is a student ID and each value is a max heap of scores.
2. Iterate through all items and push each score into the corresponding student's max heap.
3. Iterate through the map in sorted order of student IDs.
4. For each student, pop the top 5 scores from the max heap and compute their sum.
5. Store the student ID and the average in the result.
6. Return the result array.

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        K = 5
        all_scores = defaultdict(list)

        for item in items:
            student_id = item[0]
            score = item[1]
            heapq.heappush(all_scores[student_id], -score)

        solution = []
        for student_id in sorted(all_scores.keys()):
            total = 0
            for i in range(K):
                total += -heapq.heappop(all_scores[student_id])
            solution.append([student_id, total // K])

        return solution

Time & Space Complexity

• Time complexity: $O(N \log N)$
• Space complexity: $O(N)$

Where $N$ is the total number of items.

---

3. Using Map and Min Heap

Intuition

A min heap of size 5 is more space efficient than storing all scores.
As we process each score, we add it to the heap. If the heap size exceeds 5, we remove the smallest score.
This ensures the heap always contains the top 5 scores for each student.
At the end, we simply sum all elements in the heap to get the total of the top 5 scores.

Algorithm

1. Create a map where each key is a student ID and each value is a min heap.
2. For each item, push the score into the corresponding student's min heap.
3. If the heap size exceeds 5, pop the minimum element to maintain only the top 5 scores.
4. Iterate through the map in sorted order of student IDs.
5. For each student, sum all scores in the min heap and compute the average.
6. Return the result array.

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        K = 5
        all_scores = defaultdict(list)  # Using defaultdict with list for min heap

        for item in items:
            student_id = item[0]
            score = item[1]

            heapq.heappush(all_scores[student_id], score)

            if len(all_scores[student_id]) > K:
                heapq.heappop(all_scores[student_id])

        solution = []
        for student_id in sorted(all_scores.keys()):
            total = sum(all_scores[student_id])
            solution.append([student_id, total // K])

        return solution

Time & Space Complexity

• Time complexity: $O(N \log N)$
• Space complexity: $O(N)$

Where $N$ is the total number of items.

---

Common Pitfalls

Assuming Each Student Has Exactly 5 Scores

The problem guarantees each student has at least 5 scores, but they may have more. A common mistake is iterating through exactly 5 scores per student without properly handling the remaining scores. When using the sorting approach, make sure to skip all remaining scores for a student after summing their top 5. When using heaps, ensure you only extract exactly 5 elements regardless of the heap size.

Using the Wrong Heap Type

When implementing the min heap solution, some developers confuse min and max heaps. The min heap approach works by maintaining only the top 5 scores: when a new score arrives and the heap size exceeds 5, you remove the minimum. If you accidentally use a max heap, you would remove the largest scores instead, keeping the smallest ones. Similarly, when using a max heap to get top scores, ensure you are extracting (not just peeking) the maximum values.