💬 Discord
Sign In
NeetCode #527LC-1086EasyHeap / Priority QueueNC Algo100
← Back to All Problems

#527 · #1086 · High Five(前五科的均分)

📌 Problem Statement & Constraints

Given a list of [studentId, score] items, return each student's id with the floor of the average of their top five scores, sorted by id. Constraints: 1 <= items.length <= 1000, 1 <= id <= 1000, 0 <= score <= 100.

💡 Core Algorithmic Approaches

  1. Group the scores by student id.
  2. For each student, sort descending and take the top five.
  3. The result is the floor of their average.
  4. Returning in ascending id order is required, so iterate the sorted keys.

💻 Benchmark Python3 Implementation

class Solution:
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict
        scores = defaultdict(list)
        for sid, score in items:
            scores[sid].append(score)
        res = []
        for sid in sorted(scores):
            top5 = sorted(scores[sid], reverse=True)[:5]   # best five
            res.append([sid, sum(top5) // 5])               # floor average
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n) worst case: the per-student sorts dominate.
💾 Space Complexity
O(n) for the grouping.

⚠️ Interview Pitfalls & Follow-ups

  • Averaging all scores: only the top five count.
  • Using round or true division: the answer is the floor, so integer division is required.
  • Returning unsorted: the result must be ordered by student id.
  • Assuming every student has at least five scores: the slice handles fewer gracefully, but the divisor must then be the actual count -- here the constraints guarantee at least five per student.