High Five

easy hash map sorting heap

Problem

You are given a list of scores of different students, items, where items[i] = [ID_i, score_i] represents one score from a student with ID_i, where ID_i can appear multiple times. For each student, compute their top-five average: the sum of their five highest scores divided by 5 using integer division. Return the result as an array of [ID, topFiveAverage] pairs sorted by ID in ascending order.

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]]

Student 1's top five are 100, 92, 91, 87, 65 → sum 435, average 435 // 5 = 87. Student 2's top five are 100, 97, 93, 77, 76 → sum 443, average 443 // 5 = 88.

items as id:score pairs (comma-separated)

def high_five(items):
    scores = {}
    for sid, score in items:
        scores.setdefault(sid, []).append(score)
    result = []
    for sid in sorted(scores):
        top = sorted(scores[sid], reverse=True)[:5]
        result.append([sid, sum(top) // 5])
    return result

function highFive(items) {
  const scores = new Map();
  for (const [sid, score] of items) {
    if (!scores.has(sid)) scores.set(sid, []);
    scores.get(sid).push(score);
  }
  const ids = [...scores.keys()].sort((a, b) => a - b);
  return ids.map(sid => {
    const top = scores.get(sid).sort((a, b) => b - a).slice(0, 5);
    const sum = top.reduce((a, b) => a + b, 0);
    return [sid, Math.floor(sum / 5)];
  });
}

class Solution {
    public int[][] highFive(int[][] items) {
        Map<Integer, List<Integer>> scores = new TreeMap<>();
        for (int[] it : items)
            scores.computeIfAbsent(it[0], k -> new ArrayList<>()).add(it[1]);
        List<int[]> res = new ArrayList<>();
        for (Map.Entry<Integer, List<Integer>> e : scores.entrySet()) {
            List<Integer> s = e.getValue();
            s.sort(Collections.reverseOrder());
            int sum = 0;
            for (int i = 0; i < 5; i++) sum += s.get(i);
            res.add(new int[]{ e.getKey(), sum / 5 });
        }
        return res.toArray(new int[0][]);
    }
}

vector<vector<int>> highFive(vector<vector<int>>& items) {
    map<int, vector<int>> scores;
    for (auto& it : items) scores[it[0]].push_back(it[1]);
    vector<vector<int>> res;
    for (auto& [sid, s] : scores) {
        sort(s.rbegin(), s.rend());
        int sum = 0;
        for (int i = 0; i < 5; i++) sum += s[i];
        res.push_back({ sid, sum / 5 });
    }
    return res;
}

Explanation

The scores arrive all mixed together, so the first job is to group them by student. A hash map from student ID to a list of their scores does this in a single pass: scores.setdefault(sid, []).append(score).

Once each student has their own list, computing the top-five average is simple: sort the list from high to low, take the first five, sum them, and use integer division by 5.

The result must come out sorted by ID, so we iterate the IDs in sorted order (Python's sorted(scores), or a TreeMap in Java) and build the answer list.

Example: student 1 has scores 91, 92, 60, 65, 87, 100. Sorted descending the top five are 100, 92, 91, 87, 65, summing to 435, and 435 // 5 = 87.

We append each [ID, average] pair and return the list, giving one entry per student in ascending ID order.

Time: O(n log n) Space: O(n)