1086. High Five

The High Five problem is a classic introduction to combining hash maps with heaps for “top-K” style calculations. It is popular in interviews because it tests whether you can keep only the most relevant data while processing input in a single pass. While sorting every student’s full score list may seem straightforward, this problem shows why maintaining a fixed-size min-heap is the more efficient and scalable approach.

Problem statement

You’re given a list items where each entry is a pair [IDi, scorei], meaning student IDi received the score scorei. For every student, compute their top five average by:

1. Taking their five highest scores
2. Adding those five scores together
3. Dividing the sum by 5 using integer (floor) division

Return the results as a list of pairs result, where each pair is [ID, topFiveAverage]. The final list must be sorted by ID in increasing order.

Constraints:

• 1 <= items.length <= 1000
• items[i].length == 2
• 1 <= IDi <= 1000
• 0 <= scorei <= 100
• For each IDi, there will be at least five scores.

Examples

Intuition

The main idea behind this intuition is: we don’t care about all scores; we only need the top 5 scores per student. So for each student, every time we see a new score, we ask:

• Does this score belong in their top 5?
• If we already have 5 scores, we may need to discard the smallest among the top 5.

Naive approach: Sorting 

One straightforward approach is to group all scores by student ID first. Then, process students in increasing ID order, and for each student, sort their scores in descending order. Finally, for each student, take their top five scores, compute their sum, and return the average.

As simple as this solution looks, it has a major drawback: Sorting every student’s full score list can be expensive. If a student has many scores, sorting will have a time complexity of O(n log n) for that student. This is a major overkill when we only need the top 5.

Optimal approach using Min-Heap

Instead of collecting every score and sorting the entire list for each student, it is more efficient to process the input in a single pass while keeping only the information you actually need. Since the final answer depends only on the five highest scores per student, any score that is not competitive with those top five can be discarded immediately. This reduces unnecessary work (especially repeated sorting) and keeps memory usage predictable, as each student’s stored data never exceeds a small, fixed size.

A practical way to enforce this is to maintain, for each student ID, a min-heap that holds at most five scores. When a new score arrives, you insert it into that student’s heap; if the heap now contains more than five elements, you remove the smallest one. This ensures the heap always contains the best five scores seen so far for that student, without ever sorting the full set. After processing all pairs, you compute each student’s average by summing the heap and dividing by 5 using integer division, then output the results sorted by student ID.

Step-by-step algorithm

1. Create a hashmap scores_by_id mapping each studentId to a min-heap of that student’s top scores.
2. Iterate through items and for each [studentId, score]:
   1. Push score into that student’s heap.
   2. If heap size becomes > 5, pop the smallest score (so only the top 5 remain).
3. Create a list result that will store students and the average of their top five sum.
4. Iterate through each studentId in sorted order and for each student:
   1. Sum the five scores currently in that student’s heap
   2. Compute the average scores using sum // 5, and append [student_id, average] to the result.
5. Finally, return the result array.

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

1 / 5

Code implementation

Let’s look at the code for the solution we just discussed.

from collections import defaultdict
import heapq

def highFive(items):
    # Map: student_id -> min-heap of their top 5 scores
    scores_by_id = defaultdict(list)

    # Build top-5 heaps
    for studentId, score in items:
        heapq.heappush(scores_by_id[studentId], score)
        if len(scores_by_id[studentId]) > 5:
            heapq.heappop(scores_by_id[studentId])  # remove smallest among kept scores

    # Compute averages, sorted by student_id
    result = []
    for studentId in sorted(scores_by_id.keys()):
        topFiveSum = sum(scores_by_id[studentId])
        result.append([studentId, topFiveSum // 5])
        

    return result


def main():

    test_cases = [
        [[1, 91], [1, 92], [2, 93], [2, 97], [1, 60], [2, 77], [1, 65], [1, 87], [1, 100], [2, 100], [2, 76]],
        [[1, 100], [7, 100], [1, 100], [7, 100], [1, 100], [7, 100], [1, 100], [7, 100], [1, 100], [7, 100]]
    ]

    i = 0
    for items in test_cases:
        print(i + 1, ".\titems: ", items, sep="")
        print("\n\tThe top five averages are: ", highFive(items), sep="")
        print("-" * 100)
        i += 1

if __name__ == "__main__":
    main()

Time complexity 

The time complexity of this solution is O(N + S log S), where N is the number of score entries in items and S is the number of unique student IDs.

• For each of the N entries, we do a heappush (and sometimes a heappop) on a heap capped at size 5, so each heap operation is O(log 5) = O(1). This makes the first pass O(N).
• We then sort the S student IDs, which costs O(S log S).
• Summing each student’s heap is O(5) = O(1) per student, so this step is O(S).

Space complexity

The space complexity is O(S). The dictionary stores one heap per student, and each heap holds at most 5 scores, so total stored scores are at most 5S, which is O(S).

Common pitfalls and interview tips

1. Forgetting integer division: The average must be sum // 5, not float division.
2. Storing all scores unnecessarily: Sorting entire lists works, but interviewers often prefer the fixed-size heap since we only need the top 5.
3. Assuming input is already grouped/sorted: It isn’t, always build your own grouping structure and sort ID only at the end.