High Five

Easy Heaps Top K / Kth Largest / Smallest Original on LeetCode

Reported atGoldman Sachs

High Five is a easy heaps problem solved with the top k / kth largest / smallest pattern. The best approach, optimal (min-heap of size 5 per student), runs in O(n + m log m) time and O(m) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort everything) up.

Problem

You receive a list items where each entry [id, score] records one test score of the student with that id. Every student in the list has at least five scores.

For each student, compute their top-five average: the sum of their five highest scores divided by 5 using integer division (round down).

Return a list of pairs [id, topFiveAverage], sorted by id in increasing order.

Examples

Example 1

Input
items = [[4, 90], [2, 70], [4, 80], [2, 75], [4, 60], [2, 80], [4, 100], [2, 65], [4, 70], [2, 90], [4, 50]]
Output
[[2, 76], [4, 80]]
Why
Student 2 has exactly five scores: (70 + 75 + 80 + 65 + 90) / 5 = 76. Student 4's best five are 100, 90, 80, 70, 60, which average 80; the 50 is ignored.

Example 2

Input
items = [[7, 99], [7, 98], [7, 98], [7, 97], [7, 96]]
Output
[[7, 97]]
Why
488 / 5 = 97.6, and integer division rounds down to 97.

Constraints

  • 1 <= items.length <= 1000
  • items[i] = [id, score] with 1 <= id <= 1000 and 0 <= score <= 100
  • Every student that appears has at least five scores.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sort everything)O(n log n)O(n)
Optimal (min-heap of size 5 per student)O(n + m log m)O(m)

1Brute force (sort everything)

TimeO(n log n)Sorting all n pairs.
SpaceO(n)The sorted copy and the result.

Sort all pairs by id ascending and, inside the same id, by score descending. Then each student's block starts with their five best scores.

  1. Sort items by (id asc, score desc).
  2. Walk the sorted list; at the start of each new id, sum the next five scores.
  3. Append [id, sum / 5] and skip to the next id.
class Solution {
    public int[][] highFive(int[][] items) {
        int[][] a = items.clone();
        Arrays.sort(a, (p, q) -> p[0] != q[0] ? p[0] - q[0] : q[1] - p[1]);
        List<int[]> res = new ArrayList<>();
        int i = 0;
        while (i < a.length) {
            int id = a[i][0], sum = 0;
            for (int t = 0; t < 5; t++) sum += a[i + t][1];
            res.add(new int[] { id, sum / 5 });
            while (i < a.length && a[i][0] == id) i++;
        }
        return res.toArray(new int[0][]);
    }
}

2Optimal (min-heap of size 5 per student)

TimeO(n + m log m)Each push/pop is on a heap of at most 6 elements, so O(1); m distinct ids are ordered once.
SpaceO(m)Five scores per distinct student.

Keep, for every id, a min-heap that never holds more than five scores. Pushing a score and popping when the size reaches six leaves exactly the five largest. A sorted map of ids gives the output in ascending id order.

  1. For each [id, score]: heap = map[id]; offer(score); if size > 5, poll().
  2. For each id in ascending order: sum the five heap values and append [id, sum / 5].
class Solution {
    public int[][] highFive(int[][] items) {
        TreeMap<Integer, PriorityQueue<Integer>> best = new TreeMap<>();
        for (int[] it : items) {
            PriorityQueue<Integer> pq = best.computeIfAbsent(it[0], key -> new PriorityQueue<>());
            pq.offer(it[1]);
            if (pq.size() > 5) pq.poll();
        }
        int[][] res = new int[best.size()][];
        int r = 0;
        for (Map.Entry<Integer, PriorityQueue<Integer>> e : best.entrySet()) {
            int sum = 0;
            for (int s : e.getValue()) sum += s;
            res[r++] = new int[] { e.getKey(), sum / 5 };
        }
        return res;
    }
}

Edge cases to test

  • A student with exactly five scores
  • Repeated equal scores for the same student
  • Averages that are not whole numbers (round down)
  • Scores of 0

Hints

Hint 1

Group scores by student id. Only the five largest of each group matter.

Hint 2

A min-heap capped at size 5 keeps the five largest scores seen so far: when it grows to 6, drop the smallest.

FAQ

What is the best time complexity for High Five?

Optimal (min-heap of size 5 per student) runs in O(n + m log m) time and O(m) extra space. Each push/pop is on a heap of at most 6 elements, so O(1); m distinct ids are ordered once.

Which pattern does High Five use?

It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Kth Largest Element in a Stream, Top K Frequent Words.

Is there a brute force solution for High Five?

Yes. Brute force (sort everything) takes O(n log n) time and O(n) space. Sort all pairs by id ascending and, inside the same id, by score descending.

Which edge cases should I test for High Five?

A student with exactly five scores; Repeated equal scores for the same student; Averages that are not whole numbers (round down); Scores of 0.