Skip to main content
Talentd
Talentd#1 Freshers Platform
Find Work
Learn
Tools
Post a JobFreeJoin Community
TalentdTalentd

High Five - Solution & Explanation

EasyPremiumFree on FleetCodeArrayHash TableSortingHeap (Priority Queue)5 min readAsked at: Amazon, Goldman Sachs
Practice this problem

Problem Statement

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 <= 1000
  • items[i].length == 2
  • 1 <= IDi <= 1000
  • 0 <= scorei <= 100
  • For each IDi, there will be at least five scores.

Approach Overview

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.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Group Scores + SortO(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 ScoreO(n log n)O(1) extraUseful if sorting is already required for other processing

Video Solution

LeetCode 1086: High Five - Interview Prep Ep 11 • Fisher Coder • 6,738 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice High Five with our built-in code editor and test cases.

Practice on FleetCode
Previous

Determine the Winner of a Bowling Game