High Five
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 <= 1000items[i] = [id, score]with1 <= id <= 1000and0 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n log n)Sorting all n pairs.O(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.
- Sort items by (id asc, score desc).
- Walk the sorted list; at the start of each new id, sum the next five scores.
- 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][]);
}
}class Solution:
def highFive(self, items: List[List[int]]) -> List[List[int]]:
a = sorted(items, key=lambda p: (p[0], -p[1]))
res = []
i = 0
while i < len(a):
sid = a[i][0]
total = sum(a[i + t][1] for t in range(5))
res.append([sid, total // 5])
while i < len(a) and a[i][0] == sid:
i += 1
return resclass Solution {
public:
vector<vector<int>> highFive(vector<vector<int>>& items) {
vector<vector<int>> a = items;
sort(a.begin(), a.end(), [](const vector<int>& p, const vector<int>& q) {
return p[0] != q[0] ? p[0] < q[0] : p[1] > q[1];
});
vector<vector<int>> res;
size_t i = 0;
while (i < a.size()) {
int id = a[i][0], sum = 0;
for (int t = 0; t < 5; t++) sum += a[i + t][1];
res.push_back({id, sum / 5});
while (i < a.size() && a[i][0] == id) i++;
}
return res;
}
};function highFive(items) {
const a = [...items].sort((p, q) => p[0] !== q[0] ? p[0] - q[0] : q[1] - p[1]);
const res = [];
let i = 0;
while (i < a.length) {
const id = a[i][0];
let sum = 0;
for (let t = 0; t < 5; t++) sum += a[i + t][1];
res.push([id, Math.floor(sum / 5)]);
while (i < a.length && a[i][0] === id) i++;
}
return res;
}2Optimal (min-heap of size 5 per student)
O(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.O(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.
- For each [id, score]: heap = map[id]; offer(score); if size > 5, poll().
- 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;
}
}class Solution:
def highFive(self, items: List[List[int]]) -> List[List[int]]:
best = {}
for sid, score in items:
pq = best.setdefault(sid, [])
heapq.heappush(pq, score)
if len(pq) > 5:
heapq.heappop(pq)
return [[sid, sum(best[sid]) // 5] for sid in sorted(best)]class Solution {
public:
vector<vector<int>> highFive(vector<vector<int>>& items) {
map<int, priority_queue<int, vector<int>, greater<int>>> best;
for (auto& it : items) {
auto& pq = best[it[0]];
pq.push(it[1]);
if (pq.size() > 5) pq.pop();
}
vector<vector<int>> res;
for (auto& [id, pq] : best) {
int sum = 0;
while (!pq.empty()) { sum += pq.top(); pq.pop(); }
res.push_back({id, sum / 5});
}
return res;
}
};function highFive(items) {
// tiny binary min-heap helpers on plain arrays
const push = (h, v) => {
h.push(v);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (h[p] <= h[i]) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
};
const pop = (h) => {
const last = h.pop();
if (h.length === 0) return;
h[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < h.length && h[l] < h[m]) m = l;
if (r < h.length && h[r] < h[m]) m = r;
if (m === i) break;
[h[m], h[i]] = [h[i], h[m]];
i = m;
}
};
const best = new Map();
for (const [id, score] of items) {
if (!best.has(id)) best.set(id, []);
const pq = best.get(id);
push(pq, score);
if (pq.length > 5) pop(pq);
}
return [...best.keys()].sort((a, b) => a - b)
.map(id => [id, Math.floor(best.get(id).reduce((s, v) => s + v, 0) / 5)]);
}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.