Problem

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 pairsresult , whereresult[j] = [IDj, topFiveAveragej]represents the student withIDj _and theirtop five average. Sort _result byIDj inincreasing 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.

Examples

Example 1:

1
2
3
4
5

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:

1
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.

Solution

Method 1 – Hash Map and Min-Heap for Top Five

Intuition

For each student, we want to efficiently track their top five scores. We use a hash map from student ID to a min-heap (priority queue) of their scores. This allows us to always keep the top five scores for each student as we process the input.

Approach

  1. For each [id, score] in items, push score into a min-heap for that id.
  2. If the heap size exceeds 5, pop the smallest score (so only the top 5 remain).
  3. After processing all items, for each id, compute the average of the 5 scores in the heap (integer division).
  4. Return the result as a list of [id, avg], sorted by id.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<vector<int>> highFive(vector<vector<int>>& items) {
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> mp;
        for (auto& v : items) {
            mp[v[0]].push(v[1]);
            if (mp[v[0]].size() > 5) mp[v[0]].pop();
        }
        vector<vector<int>> ans;
        for (auto& [id, pq] : mp) {
            int sum = 0;
            vector<int> tmp;
            while (!pq.empty()) {
                sum += pq.top();
                tmp.push_back(pq.top());
                pq.pop();
            }
            ans.push_back({id, sum / 5});
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import (
    "container/heap"
    "sort"
)
type MinHeap []int
func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}
func highFive(items [][]int) [][]int {
    mp := map[int]*MinHeap{}
    for _, v := range items {
        id, score := v[0], v[1]
        if mp[id] == nil {
            h := &MinHeap{}
            heap.Init(h)
            mp[id] = h
        }
        heap.Push(mp[id], score)
        if mp[id].Len() > 5 {
            heap.Pop(mp[id])
        }
    }
    var ans [][]int
    for id, h := range mp {
        sum := 0
        for _, v := range *h {
            sum += v
        }
        ans = append(ans, []int{id, sum / 5})
    }
    sort.Slice(ans, func(i, j int) bool { return ans[i][0] < ans[j][0] })
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public int[][] highFive(int[][] items) {
        Map<Integer, PriorityQueue<Integer>> mp = new HashMap<>();
        for (int[] v : items) {
            mp.computeIfAbsent(v[0], k -> new PriorityQueue<>()).add(v[1]);
            if (mp.get(v[0]).size() > 5) mp.get(v[0]).poll();
        }
        int[][] ans = new int[mp.size()][2];
        int idx = 0;
        for (int id : mp.keySet()) {
            int sum = 0;
            for (int x : mp.get(id)) sum += x;
            ans[idx++] = new int[]{id, sum / 5};
        }
        Arrays.sort(ans, Comparator.comparingInt(a -> a[0]));
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.PriorityQueue
class Solution {
    fun highFive(items: Array<IntArray>): Array<IntArray> {
        val mp = mutableMapOf<Int, PriorityQueue<Int>>()
        for ((id, score) in items) {
            val pq = mp.getOrPut(id) { PriorityQueue() }
            pq.add(score)
            if (pq.size > 5) pq.poll()
        }
        val ans = mp.map { (id, pq) -> intArrayOf(id, pq.sum() / 5) }.sortedBy { it[0] }
        return ans.toTypedArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import heapq
class Solution:
    def highFive(self, items: list[list[int]]) -> list[list[int]]:
        from collections import defaultdict
        mp: dict[int, list[int]] = defaultdict(list)
        for id, score in items:
            heapq.heappush(mp[id], score)
            if len(mp[id]) > 5:
                heapq.heappop(mp[id])
        ans = [[id, sum(mp[id]) // 5] for id in mp]
        return sorted(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

use std::collections::{HashMap, BinaryHeap};
struct Solution;
impl Solution {
    pub fn high_five(items: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut mp: HashMap<i32, BinaryHeap<std::cmp::Reverse<i32>>> = HashMap::new();
        for v in items {
            let pq = mp.entry(v[0]).or_insert(BinaryHeap::new());
            pq.push(std::cmp::Reverse(v[1]));
            if pq.len() > 5 {
                pq.pop();
            }
        }
        let mut ans = vec![];
        for (id, pq) in mp {
            let sum: i32 = pq.into_iter().map(|x| x.0).sum();
            ans.push(vec![id, sum / 5]);
        }
        ans.sort();
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    highFive(items: number[][]): number[][] {
        const mp: Record<number, number[]> = {};
        for (const [id, score] of items) {
            if (!mp[id]) mp[id] = [];
            mp[id].push(score);
            if (mp[id].length > 5) {
                mp[id].sort((a, b) => a - b);
                mp[id] = mp[id].slice(1);
            }
        }
        const ans: number[][] = [];
        for (const id in mp) {
            const sum = mp[id].reduce((a, b) => a + b, 0);
            ans.push([+id, Math.floor(sum / 5)]);
        }
        ans.sort((a, b) => a[0] - b[0]);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of items, due to heap operations and sorting.
  • 🧺 Space complexity: O(n), for storing scores per student.