EasyArrayHash TableSortingHeapUpdated Sep 2026

1086. High Five

Asked at Goldman Sachs

Difficulty

Easy

Time

O(n log 5 + u log u)

Space

O(u)

Pattern

Array

Companies

1

Problem

You are given a list of exam records. Each record is a pair [studentId, score], meaning one student got one score. A student can appear many times in the list, once per score.

For every student, take their five highest scores, add them up, and divide by 5 using integer division (drop the remainder). Return one pair [studentId, average] per student, sorted by studentId in increasing order.

Every student in the input is guaranteed to have at least five scores, so you never have to worry about a student with too few scores.

Group scores by student, then keep the best five

items[1,91][1,92][2,93][2,97][1,60][2,77][1,65][1,87][1,100][2,100][2,76]012345678910Student 1's records are scattered across the list, not next to each other.student 1 top five65879192100The five best scores sum to 435, and 435 // 5 = 87.
The records arrive mixed together, so first split them by student id, then keep only the five largest scores per student.

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

Example 1
Inputitems = [[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]]
WhyStudent 1 has scores 91, 92, 60, 65, 87, 100. The best five are 100, 92, 91, 87, 65, which sum to 435, and 435 // 5 = 87. Student 2 has scores 93, 97, 77, 100, 76. Their sum is 443, and 443 // 5 = 88 (88.6 rounded down). Student 1 comes first because 1 < 2.
Example 2
Inputitems = [[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]]
WhyBoth students only ever scored 100. The top five are all 100, so the sum is 500 and 500 // 5 = 100 for each of them.

Asked At

1 companies
CompanyDifficulty
Goldman SachsEasyView all Goldman Sachs questions →

How to Think About It

1

Group scores by student id with a hash map (or a sorted map so the output is already in id order).

2

For each student you only need the five best scores. Keep a min-heap of size 5: push each score and pop whenever the heap grows past 5.

3

The average uses integer division: sum(top5) // 5.

4

Alternative: collect all scores per student, sort descending, take the first five. Simpler, slightly slower — fine at this input size.

5

Every student is guaranteed to have at least five scores.

Optimal Approach

Step 1: scores = {} mapping id to a min-heap.
Step 2: For each (id, s): push s onto scores[id]; if its size exceeds 5, pop the smallest.
Step 3: For each id in sorted order, output [id, sum(heap) // 5].

Time: O(n log 5 + u log u) where u is the number of students. Space: O(u).

A size-5 min-heap per student

heap for student 19192← topAfter the first two records the heap holds 91 and 92,with the smallest on top.heap for student 165879192100← topOnce six scores arrive, the smallest (60) is popped,leaving exactly the top five.push score, then pop if size > 5average = sum(heap) // 5sort ids before output
Push every score into the student's heap; when the heap grows past five, pop the smallest so only the top five survive.
ComplexityTime O(n log 5 + u log u)Space O(u)Each of the n records costs a heap push/pop on a heap that never holds more than 5 items, and sorting the u distinct student ids costs u log u.

What Trips People Up in Real Interviews

1

Averaging all scores instead of the top five.

2

Using floating-point division — the expected result is an integer average.

3

Forgetting to sort the output by student id.

4

Using a max-heap of all scores when a size-5 min-heap is enough.

Solution Code

O(n log 5 + u log u) time
import heapq

def highFive(items):
    scores = {}
    for sid, s in items:
        h = scores.setdefault(sid, [])
        heapq.heappush(h, s)
        if len(h) > 5:
            heapq.heappop(h)
    return [[sid, sum(scores[sid]) // 5] for sid in sorted(scores)]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the High Five problem?

High Five gives you a list of `[studentId, score]` records and asks, for each student, for the integer average of their top five scores, returned in increasing order of student id. It is a grouping plus top-k question.

How do you solve High Five?

The optimal approach runs in O(n log 5 + u log u) time and O(u) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask High Five?

High Five is asked at Goldman Sachs. It is a easy difficulty problem.

What are common mistakes on High Five?
  • Averaging all scores instead of the top five.
  • Using floating-point division — the expected result is an integer average.
  • Forgetting to sort the output by student id.
  • Using a max-heap of all scores when a size-5 min-heap is enough.