High Five

How it works

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.

Steps

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.

Complexity

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

Where N is the total number of items.

Things to watch for

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.

from typing import List
from collections import defaultdict
import heapq

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

class Solution {
private:
    int K;

public:
    vector<vector<int>> highFive(vector<vector<int>>& items) {
        this->K = 5;
        map<int, priority_queue<int, vector<int>, greater<int>>> allScores;
        for (const auto &item: items) {
            int id = item[0];
            int score = item[1];
            // insert the score in the min heap
            allScores[id].push(score);
            // remove the minimum element from the min heap in case the size of the min heap exceeds 5
            if (allScores[id].size() > this->K)
                allScores[id].pop();
        }
        vector<vector<int>> solution;
        for (auto &[id, top_scores]: allScores) {
            int total = 0;
            // min heap contains the top 5 scores
            for (int i = 0; i < this->K; ++i) {
                total += top_scores.top();
                top_scores.pop();
            }
            solution.push_back({id, total / this->K});
        }
        return solution;
    }
};