Code Implementation

from collections import defaultdict
import heapq

class Solution:
    def highFive(self, items):
        # items: List[List[int]]
        scores = defaultdict(list)
        for student_id, score in items:
            heapq.heappush(scores[student_id], score)
            if len(scores[student_id]) > 5:
                heapq.heappushpop(scores[student_id], min(scores[student_id]))
                scores[student_id].remove(min(scores[student_id]))
        result = []
        for student_id in sorted(scores.keys()):
            top_five = heapq.nlargest(5, scores[student_id])
            avg = sum(top_five) // 5
            result.append([student_id, avg])
        return result
      

#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> highFive(vector<vector<int>>& items) {
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> scores;
        for (auto& item : items) {
            int id = item[0], score = item[1];
            scores[id].push(score);
            if (scores[id].size() > 5) {
                scores[id].pop();
            }
        }
        vector<vector<int>> result;
        for (auto& p : scores) {
            int id = p.first;
            auto pq = p.second;
            int sum = 0;
            while (!pq.empty()) {
                sum += pq.top();
                pq.pop();
            }
            result.push_back({id, sum / 5});
        }
        sort(result.begin(), result.end());
        return result;
    }
};
      

import java.util.*;

class Solution {
    public int[][] highFive(int[][] items) {
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for (int[] item : items) {
            int id = item[0], score = item[1];
            map.putIfAbsent(id, new PriorityQueue<>());
            PriorityQueue<Integer> pq = map.get(id);
            pq.offer(score);
            if (pq.size() > 5) {
                pq.poll();
            }
        }
        int[][] result = new int[map.size()][2];
        int idx = 0;
        List<Integer> ids = new ArrayList<>(map.keySet());
        Collections.sort(ids);
        for (int id : ids) {
            PriorityQueue<Integer> pq = map.get(id);
            int sum = 0;
            while (!pq.isEmpty()) {
                sum += pq.poll();
            }
            result[idx][0] = id;
            result[idx][1] = sum / 5;
            idx++;
        }
        return result;
    }
}
      

/**
 * @param {number[][]} items
 * @return {number[][]}
 */
var highFive = function(items) {
    const scores = {};
    for (const [id, score] of items) {
        if (!scores[id]) scores[id] = [];
        scores[id].push(score);
    }
    const result = [];
    for (const id of Object.keys(scores).map(Number).sort((a, b) => a - b)) {
        scores[id].sort((a, b) => b - a);
        let avg = Math.floor(scores[id].slice(0, 5).reduce((a, b) => a + b, 0) / 5);
        result.push([id, avg]);
    }
    return result;
};
      

Problem Description

In the "High Five" problem, you are given a list of items, where each element is a pair [student_id, score]. Each student may have multiple scores. Your task is to compute the average of the top five scores for each student and return the result as a list of pairs [student_id, average], sorted by student_id in increasing order.

• You can assume that each student has at least five scores.
• The average should use integer division (rounded down).
• Each student's result should be included exactly once.

Thought Process

At first glance, the problem asks us to process a collection of scores, grouped by student, and find the top five for each. The naive approach would be to collect all scores for each student, sort them, and then compute the average of the highest five. However, sorting all scores for every student can be inefficient if there are many scores per student.

To optimize, we can use a min-heap (priority queue) of size 5 for each student. As we process scores, we maintain only the top five (largest) scores per student. This way, we avoid sorting large lists and keep the memory usage bounded.

Once we've processed all scores, we just compute the average of the five numbers in each heap.

Solution Approach

• Step 1: Group Scores by Student
  • Use a hash map (dictionary) where the key is student_id and the value is a collection (min-heap or array) of that student's scores.
• Step 2: Maintain Top Five Scores
  • For each new score, add it to the student's collection.
  • If we are using a min-heap and the size exceeds five, remove the smallest score. This ensures only the top five scores are kept.
• Step 3: Calculate Averages
  • For each student, sum their top five scores and perform integer division by 5 to get the average.
• Step 4: Prepare the Result
  • Return a list of [student_id, average] pairs, sorted by student_id in ascending order.

We use a hash map for fast lookups and a heap to maintain only the top scores efficiently. This approach is scalable and avoids unnecessary sorting.

Example Walkthrough

Let's use the following sample input:

• items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]

Step-by-step:

1. Group the scores:
   • Student 1: 91, 92, 60, 65, 87, 100
   • Student 2: 93, 97, 77, 100, 76
2. Keep top five scores for each:
   • Student 1: 100, 92, 91, 87, 65 (drop 60, since it's the 6th lowest)
   • Student 2: 100, 97, 93, 77, 76
3. Compute averages:
   • Student 1: (100 + 92 + 91 + 87 + 65) // 5 = 435 // 5 = 87
   • Student 2: (100 + 97 + 93 + 77 + 76) // 5 = 443 // 5 = 88
4. Return [[1,87],[2,88]]

Time and Space Complexity

• Brute-force approach:
  • Time: O(N log N), where N is the number of scores. For each student, we sort all their scores.
  • Space: O(N), to store all scores.
• Optimized approach (using min-heap):
  • Time: O(N log 5) = O(N), because heap operations are O(log 5), and 5 is a constant.
  • Space: O(S), where S is the number of students times 5 (since we store only five scores per student).

The optimized approach is much more efficient, especially when students have many scores.

Summary

The "High Five" problem is solved efficiently by grouping scores per student and maintaining only their top five using a min-heap. This avoids unnecessary sorting and reduces memory usage. The approach leverages hash maps for grouping and heaps for efficient top-k management, resulting in a clean, scalable solution. The final result is sorted and uses integer division as required.