High Five LeetCode Solution

Difficulty Level Easy
Frequently asked in Amazon Goldman Sachs
Array Hash Table Priority QueueViews 3388

Problem Statement:

The High Five LeetCode Solution – Given a list of scores of different students named “item”, where the “item” has two fields item[0] represents the student’s id, and item[1] represents the student’s score eg. item[i]=[IDi, SCOREi]

Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average.

Note: A student’s top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.

 

Example:

Input: 
items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
Output: 
[[1,87],[2,88]]

Explanation

For student id 1 : scores -> 91, 92, 60, 65, 87, 100

The top five scores for student 1: 100, 92, 91, 87, 65

So the average of top five scores for student 1 : (100 + 92 + 91 + 87 + 65 ) / 5 = 87

In the same way,

For student id 2 : scores -> 93, 97, 77, 100, 76

The top five scores for student 2: 100, 97, 93, 77, 76

So the average of top five scores for student 2: (100 + 97 + 93 + 77 + 76 ) / 5 = 88

Output:  [[1,87],[2,88]]

 

Input:

Input:
items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]

Output:

Output:
[[1,100],[7,100]]

Explanation

For student id 1 : scores -> 100, 100, 100, 100, 100

The top five scores for student 1: 100, 100, 100, 100, 100

So the average of top five scores for student 1 : (100 + 100 + 100 + 100 + 100 ) / 5 = 100

In the same way,

For student id 7 : scores -> 100, 100, 100, 100, 100

The top five scores for student 7: 100, 100, 100, 100, 100

So the average of top five scores for student 7: (100 + 100 + 100 + 100 + 100 ) / 5 = 100

Output: [[1,100],[7,100]]

 

Approach:

Idea

We maintain a max heap of all the scores for every id so that we can easily get the top five elements for each of the ids by obtaining the first 5 elements from the max heap. For storing the ids of the students as the key element we also need a map data structure.

High Five LeetCode Solution

  1. First, create a map of type <integer type, priority_queue> and iterate through all the elements of the given list “item” and push the student’s id and the corresponding score of the student on the map.
  2. As we use a max heap to store the scores of a student, it ensures that we’ll always get the maximum score at the top of the priority_queue.
  3. Now we iterate through the map and take the id and the first five elements of the max heap and calculate their average value.
  4. Finally, we push the id and average value into the result.
  5. Return the result.

Code:

C++ Program of High Five

class Solution {
public:
    vector<vector<int>> highFive(vector<vector<int>>& items) {
        vector<vector<int>> res;
        map<int, priority_queue<int>> mpp;
        for(auto i:items){
            int id=i[0];
            int score=i[1];
            mpp[id].push(score);
        }
        for(auto i:mpp){
            int id = i.first;
            auto scores = i.second;
            int val=0, count=1;
            while(count <= 5){
                val += scores.top();
                scores.pop();
                count++;
            }
            val/=5;
            res.push_back({id, val});
        }
        return res;
    }
};

 

Java Program of High Five

class Solution {
    public int[][] highFive(int[][] items) {
        Map<Integer,PriorityQueue<Integer>> mpp = new HashMap<>();
        
        for(int[] info : items){
            int id = info[0];
            int score = info[1];
            PriorityQueue<Integer> pq = mpp.getOrDefault(id,new PriorityQueue<>());
            pq.add(score);
            if(pq.size()>5)
                pq.poll();
            mpp.put(id,pq);
        }
        
        int [][] res = new int[mpp.size()][2];
        int index=0;
        for(Map.Entry<Integer,PriorityQueue<Integer>> entry : mpp.entrySet()){
            int val=0;
            int id = entry.getKey();
            PriorityQueue<Integer> pq = entry.getValue();
            while(!pq.isEmpty())
                val+=pq.poll();
            res[index][0] = id;
            res[index++][1] = val/5;
        }
        
        return res;
    }
}

 

Complexity Analysis for High Five LeetCode Solution:

Time Complexity:

The time complexity of the code is O(NlogN) as LogN for putting the scores of the given “item” into the priority queue and we need to traverse all N elements so the overall time complexity will be O(NlogN).

Space Complexity:

The space complexity will be O(N) as we need a hash map to store the ids of the students and their corresponding scores.

 

Translate »