Domain 1EasyCORE

High Five

The problem requires calculating the top five average scores for each student given a list of scores. Each score is represented by a pair `[IDi, scorei]`, where `IDi` is the student's ID and `scorei` is their score. The output should be an array of pairs `[IDj, topFiveAveragej]`, sorted by `IDj`. The average should be calculated using integer division.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table#Sort

1086. High Five

Model: qwen2.5-coder:14b
Topics: Array,Hash Table,Sort
FAANG asked: 0
Acceptance rate: 77.3%


Problem Breakdown

The problem requires calculating the top five average scores for each student given a list of scores. Each score is represented by a pair [IDi, scorei], where IDi is the student’s ID and scorei is their score. The output should be an array of pairs [IDj, topFiveAveragej], sorted by IDj. The average should be calculated using integer division.

Inputs:

  • A list of scores items, where each item is a pair [IDi, scorei].

Outputs:

  • An array of pairs [IDj, topFiveAveragej], sorted by IDj.

Implicit Constraints:

  • Each student has at least five scores.
  • IDs are between 1 and 1000.
  • Scores are between 0 and 100.

Intuition

The brute-force approach would involve sorting all the scores for each student, then selecting the top five scores to calculate the average. This approach is inefficient because it requires sorting multiple times, which has a time complexity of O(n log n) per student.

A better approach involves using a hash table (dictionary in Python) to group scores by student ID and then maintaining a sorted list of scores for each student. By keeping only the top five scores, we can efficiently calculate the average without needing to sort all scores again.

Approach

  1. Initialize a Dictionary: Use a dictionary where keys are student IDs and values are lists of scores.
  2. Populate the Dictionary: Iterate through the items list and append each score to the corresponding student’s list in the dictionary.
  3. Sort and Trim Scores: For each student, sort their list of scores in descending order and keep only the top five scores.
  4. Calculate Averages: Compute the integer average of the top five scores for each student.
  5. Prepare the Result: Create a result list containing pairs of [IDj, topFiveAveragej] and sort it by IDj.

Complexity Analysis

  • Time Complexity: O(n log n) due to sorting the scores for each student. Here, n is the number of items in the input list.
  • Space Complexity: O(n) for storing the dictionary and the result list.

Solution

def highFive(items):
    from collections import defaultdict
    
    # Step 1: Initialize a dictionary to store scores by student ID
    student_scores = defaultdict(list)
    
    # Step 2: Populate the dictionary with scores
    for student_id, score in items:
        student_scores[student_id].append(score)
    
    # Step 3: Sort and trim top five scores for each student
    for student_id in student_scores:
        student_scores[student_id].sort(reverse=True)
        student_scores[student_id] = student_scores[student_id][:5]
    
    # Step 4: Calculate the average of the top five scores
    result = []
    for student_id, scores in sorted(student_scores.items()):
        average_score = sum(scores) // len(scores)
        result.append([student_id, average_score])
    
    # Step 5: Return the result list
    return result

Edge Cases Handled

  • Multiple Students with Different IDs: The dictionary ensures that each student’s scores are grouped correctly.
  • Scores Less Than Five: Although the problem guarantees at least five scores per student, this approach naturally handles cases where there might be more than five scores by only considering the top five.
  • Sorting and Integer Division: The sorting ensures the top five scores are selected, and integer division is used to calculate the average as required.