High Five

Solution

Let n to be the total number of items in items.

HashMap

Complexity

time: $O(n\log(n))$
space: $O(n)$

from collections import defaultdict
def highFive(self, items: List[List[int]]) -> List[List[int]]:
    map = defaultdict(list)
    n = len(items)
    for i in range(n):
        id = items[i][0]
        score = items[i][1]
        map[id].append(score)
    
    res = []
    # for each student, sort grades and get top 5 average
    for id in sorted(map.keys()):
        scores = sorted(map[id], reverse=True)
        score_sum = 0
        for i in range(5):
            score_sum += scores[i]
        avg = score_sum // 5
        res.append([id, avg])
    
    return res

Priority Queue

Complexity

time: $O(n\log(n))$
space: $O(n)$

from collections import defaultdict
from heapq import heappush, heappop

def highFive(self, items: List[List[int]]) -> List[List[int]]:
    # [id, score]
    scores = defaultdict(list)
    for (id, score) in items:
        heappush(scores[id], score)
        if len(scores[id]) > 5:
            heappop(scores[id])
    
    # calc avg
    res = []
    for id in sorted(scores):
        res.append([id, sum(scores[id]) // len(scores[id])])
    return res