Is High Five easy or hard?

High Five is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly involves recognizing that only the top five scores matter and choosing a data structure such as a min heap to maintain them efficiently.

High Five Python/Java solution

Most implementations follow the same pattern: map each student ID to a priority queue storing at most five scores. Python typically uses heapq, while Java uses PriorityQueue. After processing all pairs, compute the average of the five scores stored for each student and return results sorted by ID.

How to solve High Five in O(n)?

Maintain a hash map from student ID to a min heap that stores at most five scores. Insert each score and remove the smallest whenever the heap grows beyond size five. After processing all records, sum the five values in each heap and divide by five. Since heap operations cost log 5, the overall runtime behaves like O(n).

What is the best approach for High Five?

The most efficient solution uses a hash map combined with a min heap of size five per student. As scores are processed, each score is pushed into the student's heap and the smallest score is removed when the heap exceeds size five. This guarantees the heap always contains the student's top five scores. The overall complexity is O(n log 5), which is effectively O(n).

Is High Five asked at Google/Amazon/Meta?

High Five is commonly seen in interviews at companies that test practical data structure usage, including heap and hash map problems. It has appeared in interview preparation sets associated with companies like Google and Amazon. The problem focuses on efficiently tracking top-k values per key.

What data structure is used in High Five?

The key data structures are a hash table to group scores by student ID and a min heap (priority queue) to keep the top five scores. The heap ensures that the smallest score among the top five can be removed quickly when a better score appears.

What is the time complexity of High Five?

The optimal heap-based solution runs in O(n log 5) time where n is the number of score entries. Because the heap size never exceeds five, log 5 is constant, making the runtime effectively O(n). Space complexity is O(n) due to storing scores across student heaps.

Description Hints 3 Solution Video 12:53

1086. High Five

Easy74.5% acceptance2 companiesPremium elsewhere, free here

Given a list of the scores of different students, items, where items[i] = [ID_i, score_i] represents one score from a student with ID_i, calculate each student's top five average.

Return the answer as an array of pairs result, where result[j] = [ID_j, topFiveAverage_j] represents the student with ID_j and their top five average. Sort result by ID_j 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 <= 1000
items[i].length == 2
1 <= ID_i <= 1000
0 <= score_i <= 100
For each ID_i, there will be at least five scores.

Asked at 2 companies

Goldman Sachs Amazon

Topics

Hints open one at a time

Hint 1

How can we solve the problem if we have just one student?

Hint 2

Given an student sort their grades and get the top 5 average.

Hint 3

Generalize the idea to do it for many students.

12:53

Still stuck?Read the written solution, or watch a walkthrough.

Open solution