LeetCode 1086: High Five

Problem Restatement

We are given a list of [id, score] pairs.

For each student, compute the average of their top 5 scores (integer division).

Return the result sorted by student ID.

The official constraints state that each student has at least 5 scores.

Input and Output

Function shape:

def highFive(items: list[list[int]]) -> list[list[int]]:
    ...

Examples

Example 1:

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

Student 1 scores: [91,92,60,65,87,100]. Top 5: [100,92,91,87,65]. Avg = 87.

Student 2 scores: [93,97,77,100,76]. Top 5: [100,97,93,77,76]. Avg = 88.

Answer:

[[1,87],[2,88]]

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import defaultdict

class Solution:
    def highFive(self, items: list[list[int]]) -> list[list[int]]:
        scores = defaultdict(list)
        for id_, score in items:
            scores[id_].append(score)

        return [
            [id_, sum(sorted(s, reverse=True)[:5]) // 5]
            for id_, s in sorted(scores.items())
        ]

Testing

def run_tests():
    s = Solution()

    result = s.highFive([[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]])
    assert result == [[1,87],[2,88]]

    print("all tests passed")

run_tests()