Problem Description

You are given a list of student scores where each entry contains a student ID and a score. Multiple scores can exist for the same student. Your task is to calculate each student's "top five average" score.

The top five average for a student is calculated by:

1. Taking their 5 highest scores
2. Summing these 5 scores
3. Dividing by 5 using integer division (discarding any remainder)

The input items is a list where each element is [IDᵢ, scoreᵢ] representing a score for a student with that ID.

You need to return a list of pairs [IDⱼ, topFiveAverageⱼ] where:

• Each pair represents a student ID and their calculated top five average
• The results must be sorted by student ID in increasing order
• Only students who have at least one score should appear in the output

For example, if a student with ID 1 has scores [90, 85, 95, 88, 92, 87, 91], their top 5 scores would be [95, 92, 91, 90, 88], giving a sum of 456, and their top five average would be 456 // 5 = 91.

Intuition

The key insight is that we need to group all scores by student ID first, since the input list contains scores scattered across different students. Once we have all scores for each student grouped together, we can easily find their top 5 scores.

We can think of this problem in two phases:

1. Collecting phase: As we iterate through the input, we gather all scores for each student. A dictionary (or hashmap) is perfect for this - we use the student ID as the key and maintain a list of all their scores as the value.

2. Processing phase: For each student, we need their 5 highest scores. Instead of sorting all their scores (which would take O(n log n) time), we can use a more efficient approach with nlargest(5, scores) which finds the 5 largest elements in O(n log 5) = O(n) time using a heap internally.

The reason we track the maximum student ID during the collecting phase is to ensure we process students in order from ID 1 to the maximum ID. This guarantees our output is sorted by student ID as required.

For each student ID from 1 to max, we check if they have any scores. If they do, we:

• Extract their top 5 scores using nlargest(5, xs)
• Sum these scores and perform integer division by 5
• Add the [ID, average] pair to our result

This approach is efficient because we only sort/process the scores we need (top 5) rather than sorting all scores for each student.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses a dictionary-based approach to group and process student scores:

Step 1: Initialize Data Structures

• Create a defaultdict(list) to store scores for each student ID. This allows us to append scores without checking if the key exists.
• Initialize a variable m to track the maximum student ID encountered.

Step 2: Group Scores by Student ID

for i, x in items:
    d[i].append(x)
    m = max(m, i)

• Iterate through each [student_id, score] pair in the input
• Append each score to the list associated with that student's ID in the dictionary
• Update the maximum student ID seen

Step 3: Calculate Top Five Averages

for i in range(1, m + 1):
    if xs := d[i]:
        avg = sum(nlargest(5, xs)) // 5
        ans.append([i, avg])

• Iterate through all possible student IDs from 1 to the maximum ID found
• For each ID, check if the student has any scores using the walrus operator :=
• If scores exist:
  • Use nlargest(5, xs) to efficiently find the 5 highest scores. This function uses a min-heap internally and runs in O(n) time where n is the number of scores for that student
  • Sum these top 5 scores
  • Perform integer division by 5 to get the average
  • Append [student_id, average] to the result list

Key Implementation Details:

• The nlargest function from the heapq module is crucial here - it's more efficient than sorting all scores when we only need the top 5
• Integer division // ensures we get the floor of the average as required
• By iterating from 1 to max ID, we automatically ensure the output is sorted by student ID
• The walrus operator := allows us to both assign and check if a student has scores in a single expression

Time Complexity: O(n + m*k) where n is the total number of scores, m is the number of unique students, and k is the average number of scores per student.

Space Complexity: O(n) to store all scores in the dictionary.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input: items = [[1, 90], [1, 85], [2, 88], [1, 95], [2, 92], [1, 88], [2, 87], [1, 92], [2, 91], [1, 87], [2, 85]]

Step 1: Group scores by student ID

We iterate through each [student_id, score] pair and build our dictionary:

Processing [1, 90]: d = {1: [90]}, m = 1
Processing [1, 85]: d = {1: [90, 85]}, m = 1
Processing [2, 88]: d = {1: [90, 85], 2: [88]}, m = 2
Processing [1, 95]: d = {1: [90, 85, 95], 2: [88]}, m = 2
Processing [2, 92]: d = {1: [90, 85, 95], 2: [88, 92]}, m = 2
Processing [1, 88]: d = {1: [90, 85, 95, 88], 2: [88, 92]}, m = 2
Processing [2, 87]: d = {1: [90, 85, 95, 88], 2: [88, 92, 87]}, m = 2
Processing [1, 92]: d = {1: [90, 85, 95, 88, 92], 2: [88, 92, 87]}, m = 2
Processing [2, 91]: d = {1: [90, 85, 95, 88, 92], 2: [88, 92, 87, 91]}, m = 2
Processing [1, 87]: d = {1: [90, 85, 95, 88, 92, 87], 2: [88, 92, 87, 91]}, m = 2
Processing [2, 85]: d = {1: [90, 85, 95, 88, 92, 87], 2: [88, 92, 87, 91, 85]}, m = 2

After grouping:

• Student 1 has scores: [90, 85, 95, 88, 92, 87]
• Student 2 has scores: [88, 92, 87, 91, 85]
• Maximum student ID: m = 2

Step 2: Calculate top five averages for each student

We iterate from ID 1 to ID 2:

For Student ID 1:

• Scores: [90, 85, 95, 88, 92, 87]
• Apply nlargest(5, scores) → [95, 92, 90, 88, 87]
• Sum: 95 + 92 + 90 + 88 + 87 = 452
• Average: 452 // 5 = 90
• Add to result: [[1, 90]]

For Student ID 2:

• Scores: [88, 92, 87, 91, 85]
• Apply nlargest(5, scores) → [92, 91, 88, 87, 85] (all 5 scores)
• Sum: 92 + 91 + 88 + 87 + 85 = 443
• Average: 443 // 5 = 88
• Add to result: [[1, 90], [2, 88]]

Final Output: [[1, 90], [2, 88]]

The result is automatically sorted by student ID since we processed IDs in increasing order from 1 to 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m * k log k) where n is the number of items, m is the number of unique students, and k is the number of scores per student.

• Iterating through all items to build the dictionary: O(n)
• For each unique student (m students), we use nlargest(5, xs) which has complexity O(k log 5) = O(k) for finding the 5 largest elements from k scores using a min-heap approach
• Since we iterate through all student IDs from 1 to m: O(m * k)
• Overall: O(n + m * k)

In the worst case where each student has many scores, this could be simplified to O(n log n) if we consider k could be proportional to n/m.

Space Complexity: O(n)

• The dictionary d stores all n scores across all students: O(n)
• The ans list stores at most m student-average pairs: O(m)
• The nlargest function uses internal space of O(5) = O(1) for maintaining a heap of size 5
• Since m ≤ n (number of students cannot exceed number of items), the overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Students Have At Least 5 Scores

One critical pitfall in this problem is assuming every student has at least 5 scores. The problem statement doesn't guarantee this, and the code could fail or produce incorrect results if a student has fewer than 5 scores.

The Issue: When using nlargest(5, scores), if a student has fewer than 5 scores (say only 3), the function will return all available scores. The subsequent division by 5 would then be incorrect.

Example of the Problem:

# If student 1 has only 3 scores: [90, 85, 88]
top_five_scores = nlargest(5, [90, 85, 88])  # Returns [90, 88, 85]
average = sum([90, 88, 85]) // 5  # 263 // 5 = 52 (incorrect!)
# The correct average should be 263 // 3 = 87

Solution:

def highFive(self, items: List[List[int]]) -> List[List[int]]:
    student_scores = defaultdict(list)
    max_student_id = 0
  
    for student_id, score in items:
        student_scores[student_id].append(score)
        max_student_id = max(max_student_id, student_id)
  
    result = []
  
    for student_id in range(1, max_student_id + 1):
        scores = student_scores[student_id]
        if scores:
            # Handle cases where student has fewer than 5 scores
            top_scores = nlargest(5, scores)
            num_scores = min(len(scores), 5)
            average = sum(top_scores) // num_scores
            result.append([student_id, average])
  
    return result

2. Inefficient Sorting Approach

Another common mistake is sorting all scores for each student when you only need the top 5.

The Issue:

# Inefficient approach
for student_id, scores_list in student_scores.items():
    scores_list.sort(reverse=True)  # O(k log k) where k is number of scores
    average = sum(scores_list[:5]) // 5

This sorts all scores even if a student has hundreds of scores, when we only need the top 5.

Better Approach: Using nlargest(5, scores) is more efficient as it uses a min-heap internally and runs in O(k) time for finding the 5 largest elements, rather than O(k log k) for a full sort.

3. Not Handling Sparse Student IDs

If student IDs are not consecutive (e.g., IDs are 1, 3, 100), iterating from 1 to max_id creates unnecessary iterations.

More Efficient Solution for Sparse IDs:

def highFive(self, items: List[List[int]]) -> List[List[int]]:
    student_scores = defaultdict(list)
  
    for student_id, score in items:
        student_scores[student_id].append(score)
  
    result = []
  
    # Iterate only through existing student IDs
    for student_id in sorted(student_scores.keys()):
        scores = student_scores[student_id]
        top_scores = nlargest(5, scores)
        num_scores = min(len(scores), 5)
        average = sum(top_scores) // num_scores
        result.append([student_id, average])
  
    return result

This approach only processes students that actually exist in the input, making it more efficient when student IDs are sparse.