0694EasyArrayHash TableSortingHeap (Priority Queue)

Top Five Average per Apprentice

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A workshop logs one entry per weld inspection. Entry records[i] = [badge, score] says that the apprentice wearing badge scored score on one inspection. An apprentice may appear many times, and the entries are in no particular order.

For every badge that appears, take that apprentice's five highest scores and average them, rounding the average down to a whole number. Repeated scores count separately, so an apprentice with five inspections all scored 80 has five scores of 80.

Return one entry [badge, average] per badge that appears, ordered by badge from smallest to largest.

Examples

Example 1

Input: records = [[7, 100], [7, 100], [7, 100], [7, 100], [7, 99]]
Output: [[7, 99]]

Badge 7 has exactly five scores, adding to 499. Dividing by five and rounding down gives 99.

Example 2

Input: records = [[1, 90], [1, 80], [1, 70], [1, 60], [1, 50], [1, 40]]
Output: [[1, 70]]

The score of 40 is not among the badge's five highest, so the average is taken over 90, 80, 70, 60 and 50, which add to 350.

Example 3

Input: records = [[1000, 0], [1000, 0], [1000, 0], [1000, 0], [1000, 0], [3, 100], [3, 100], [3, 100], [3, 100], [3, 100]]
Output: [[3, 100], [1000, 0]]

Badge 3 averages 100 and badge 1000 averages 0. Badge 3 is listed first because the answer is ordered by badge, not by where the entries appear in the log.

Constraints

5 <= records.length <= 1000
records[i].length == 2
0 <= records[i][j] <= 1000
Each entry is [badge, score] with 1 <= badge <= 1000 and 0 <= score <= 100.
Every badge that appears has at least five entries.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def top_five_averages(records: list[list[int]]) -> list[list[int]]:

Java

public int[][] topFiveAverages(int[][] records)

The intended approach

Time O(n log n) for n entries, dominated by sorting the score groups and the badge keys.Space O(n) for the grouped scores and the returned list.

Group the scores by badge in a hash table in one pass over the log. Then visit the badges in increasing order, sort each badge's scores from high to low, add the leading five and divide by five with integer division to get that badge's figure.

Pythonentry point: top_five_averages

def top_five_averages(records):
    scores = {}
    for badge, score in records:
        if badge in scores:
            scores[badge].append(score)
        else:
            scores[badge] = [score]
    out = []
    for badge in sorted(scores):
        run = sorted(scores[badge], reverse=True)[:5]
        out.append([badge, sum(run) // 5])
    return out

The obvious version

Collect the badges that appear, then for each badge in increasing order rescan the whole log for its scores and pull out the largest one five times over by linear search, adding as it goes. Quadratic, and it never sorts a score list.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_top_five_averages(records):
    badges = []
    for badge, _score in records:
        if badge not in badges:
            badges.append(badge)
    badges.sort()
    out = []
    for badge in badges:
        pool = [s for b, s in records if b == badge]
        total = 0
        for _ in range(5):
            top = pool[0]
            at = 0
            for i in range(1, len(pool)):
                if pool[i] > top:
                    top = pool[i]
                    at = i
            total += top
            pool.pop(at)
        out.append([badge, total // 5])
    return out

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in