High Five — LeetCode 1086 Python Solution

The 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 pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average.

Example

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.

Python solution

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        d = defaultdict(list)
        m = 0
        for i, x in items:
            d[i].append(x)
            m = max(m, i)
        ans = []
        for i in range(1, m + 1):
            if xs := d[i]:
                avg = sum(nlargest(5, xs)) // 5
                ans.append([i, avg])
        return ans

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1086. High Five is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems