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 byIDj.
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
- Initialize a Dictionary: Use a dictionary where keys are student IDs and values are lists of scores.
- Populate the Dictionary: Iterate through the
itemslist and append each score to the corresponding student’s list in the dictionary. - Sort and Trim Scores: For each student, sort their list of scores in descending order and keep only the top five scores.
- Calculate Averages: Compute the integer average of the top five scores for each student.
- Prepare the Result: Create a result list containing pairs of
[IDj, topFiveAveragej]and sort it byIDj.
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.