Skip to content

1086. High Five 👍

  • Time: $O(n\log 5) = O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  vector<vector<int>> highFive(vector<vector<int>>& items) {
    vector<vector<int>> ans;
    map<int, priority_queue<int, vector<int>, greater<int>>> idToScores;

    for (const vector<int>& item : items) {
      const int id = item[0];
      const int score = item[1];
      auto& scores = idToScores[id];
      scores.push(score);
      if (scores.size() > 5)
        scores.pop();
    }

    for (auto& [id, scores] : idToScores) {
      int sum = 0;
      while (!scores.empty())
        sum += scores.top(), scores.pop();
      ans.push_back({id, sum / 5});
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int[][] highFive(int[][] items) {
    List<int[]> ans = new ArrayList<>();
    Map<Integer, PriorityQueue<Integer>> idToScores = new TreeMap<>();

    for (int[] item : items) {
      final int id = item[0];
      final int score = item[1];
      idToScores.putIfAbsent(id, new PriorityQueue<>());
      PriorityQueue<Integer> scores = idToScores.get(id);
      scores.add(score);
      if (scores.size() > 5)
        scores.poll();
    }

    for (Map.Entry<Integer, PriorityQueue<Integer>> entry : idToScores.entrySet()) {
      final int id = entry.getKey();
      PriorityQueue<Integer> scores = entry.getValue();
      int sum = 0;
      while (!scores.isEmpty())
        sum += scores.poll();
      ans.add(new int[] {id, sum / 5});
    }

    return ans.toArray(int[][] ::new);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def highFive(self, items: list[list[int]]) -> list[list[int]]:
    idToScores = collections.defaultdict(list)

    for id, score in items:
      heapq.heappush(idToScores[id], score)
      if len(idToScores[id]) > 5:
        heapq.heappop(idToScores[id])

    return [[id, sum(scores) // 5] for id, scores in sorted(idToScores.items())]