# Reward Top K Students
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reward-top-k-students)
Canonical: https://scaleengineer.com/dsa/problems/reward-top-k-students
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String, Heap (Priority Queue)
**Companies:** [Booking.com](https://scaleengineer.com/companies/booking.com)
---
## Problem
You are given two string arrays `positive_feedback` and `negative_feedback`, containing the words denoting positive and negative feedback, respectively. Note that **no** word is both positive and negative.

Initially every student has `0` points. Each positive word in a feedback report **increases** the points of a student by `3`, whereas each negative word **decreases** the points by `1`.

You are given `n` feedback reports, represented by a **0-indexed** string array `report` and a **0-indexed** integer array `student_id`, where `student_id[i]` represents the ID of the student who has received the feedback report `report[i]`. The ID of each student is **unique**.

Given an integer `k`, return _the top_ `k` _students after ranking them in **non-increasing** order by their points_. In case more than one student has the same points, the one with the lower ID ranks higher.

**Example 1:**

**Input:** positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2
**Output:** [1,2]
**Explanation:** 
Both the students have 1 positive feedback and 3 points but since student 1 has a lower ID he ranks higher.

**Example 2:**

**Input:** positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2
**Output:** [2,1]
**Explanation:** 
- The student with ID 1 has 1 positive feedback and 1 negative feedback, so he has 3-1=2 points. 
- The student with ID 2 has 1 positive feedback, so he has 3 points. 
Since student 2 has more points, [2,1] is returned.

**Constraints:**

* `1 <= positive_feedback.length, negative_feedback.length <= 104`
* `1 <= positive_feedback[i].length, negative_feedback[j].length <= 100`
* Both `positive_feedback[i]` and `negative_feedback[j]` consists of lowercase English letters.
* No word is present in both `positive_feedback` and `negative_feedback`.
* `n == report.length == student_id.length`
* `1 <= n <= 104`
* `report[i]` consists of lowercase English letters and spaces `' '`.
* There is a single space between consecutive words of `report[i]`.
* `1 <= report[i].length <= 100`
* `1 <= student_id[i] <= 109`
* All the values of `student_id[i]` are **unique**.
* `1 <= k <= n`

# Approaches
## Sorting
This approach first calculates the score for every student and then sorts all the students based on the ranking criteria. Finally, it selects the top `k` students from the sorted list.
**Time:** O(F*L + M*W + S log S), where `F*L` is the time to build feedback sets, `M*W` is the time to process all reports (`M` reports with `W` words each), and `S log S` is the time to sort the `S` unique students. The dominant part is `S log S` for sorting. · **Space:** O(F*L + S), where `F` is the total number of feedback words, `L` is their average length, and `S` is the number of unique students. This space is used for storing feedback words in sets and student scores in a map and list.
**Pros:** Relatively simple to understand and implement.; Uses standard library functions for sorting.
**Cons:** Sorting all `S` students is inefficient if `k` is much smaller than `S`. The complexity is `O(S log S)` regardless of `k`.
### Explanation
```java
import java.util.*;

class Solution {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        Set<String> positiveWords = new HashSet<>(Arrays.asList(positive_feedback));
        Set<String> negativeWords = new HashSet<>(Arrays.asList(negative_feedback));
        
        Map<Integer, Integer> scores = new HashMap<>();
        for (int i = 0; i < report.length; i++) {
            int id = student_id[i];
            String[] words = report[i].split(" ");
            int score = 0;
            for (String word : words) {
                if (positiveWords.contains(word)) {
                    score += 3;
                } else if (negativeWords.contains(word)) {
                    score -= 1;
                }
            }
            scores.put(id, scores.getOrDefault(id, 0) + score);
        }
        
        List<int[]> studentList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : scores.entrySet()) {
            studentList.add(new int[]{entry.getKey(), entry.getValue()});
        }
        
        // Sort: higher points first, then lower ID first.
        Collections.sort(studentList, (a, b) -> {
            if (a[1] != b[1]) {
                return b[1] - a[1]; // Descending by score
            } else {
                return a[0] - b[0]; // Ascending by ID
            }
        });
        
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(studentList.get(i)[0]);
        }
        
        return result;
    }
}
```
### Algorithm
*   **Step 1: Pre-process Feedback Words.** To allow for efficient lookups, we store the `positive_feedback` and `negative_feedback` words into two separate Hash Sets. This reduces the time to check if a word is positive or negative to O(1) on average.
*   **Step 2: Calculate Student Scores.** We use a Hash Map to store the points for each student, with the student's ID as the key and their score as the value. We iterate through each report in the `report` array. For each report, we split it into words, and for each word, we check if it's in our positive or negative feedback sets. We calculate the total score for the report and add it to the corresponding student's total score in the Hash Map.
*   **Step 3: Create and Sort Student List.** We convert the Hash Map of scores into a list of student objects or pairs, where each element contains a student's ID and their final score. We then sort this list using a custom comparator. The comparator first compares students by their points in descending order. If two students have the same number of points, it compares them by their student ID in ascending order.
*   **Step 4: Extract Top K Students.** After sorting, the top `k` students are simply the first `k` elements in the list. We extract their IDs and return them as the result.

## Min-Heap (Priority Queue)
This approach is more efficient, especially when `k` is much smaller than the total number of students. After calculating all student scores, it uses a min-heap of size `k` to find the top `k` students in a single pass. This avoids the cost of sorting the entire list of students.
**Time:** O(F*L + M*W + S log k), where `F*L` is time to build feedback sets, `M*W` is time to process reports, and `S log k` is time to process `S` students with a heap of size `k`. This is more efficient than `S log S` when `k` is small. · **Space:** O(F*L + S + k), where `F*L` is for feedback words, `S` is for student scores, and `k` is for the heap.
**Pros:** More efficient than full sorting, with a time complexity of `O(S log k)` for the selection part.; Ideal for scenarios where `k` is much smaller than the total number of students.
**Cons:** Slightly more complex to implement due to the custom comparator for the priority queue and the final extraction step.
### Explanation
```java
import java.util.*;

class Solution {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        Set<String> positiveWords = new HashSet<>(Arrays.asList(positive_feedback));
        Set<String> negativeWords = new HashSet<>(Arrays.asList(negative_feedback));
        
        Map<Integer, Integer> scores = new HashMap<>();
        for (int i = 0; i < report.length; i++) {
            int id = student_id[i];
            String[] words = report[i].split(" ");
            int score = 0;
            for (String word : words) {
                if (positiveWords.contains(word)) {
                    score += 3;
                } else if (negativeWords.contains(word)) {
                    score -= 1;
                }
            }
            scores.put(id, scores.getOrDefault(id, 0) + score);
        }
        
        // Min-heap to find top k students.
        // Comparator: lower score first, then higher ID first.
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1]; // Ascending by score
            } else {
                return b[0] - a[0]; // Descending by ID
            }
        });
        
        for (Map.Entry<Integer, Integer> entry : scores.entrySet()) {
            minHeap.offer(new int[]{entry.getKey(), entry.getValue()});
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        
        LinkedList<Integer> result = new LinkedList<>();
        while (!minHeap.isEmpty()) {
            result.addFirst(minHeap.poll()[0]);
        }
        
        return result;
    }
}
```
### Algorithm
*   **Step 1 & 2: Pre-processing and Score Calculation.** These steps are identical to the sorting approach. We use Hash Sets for feedback words and a Hash Map to calculate the total score for each student.
*   **Step 3: Maintain a Min-Heap of Top K Students.** We create a Min-Heap (implemented as a `PriorityQueue` in Java) with a maximum size of `k`. The heap's ordering is crucial: it's designed to keep the "worst" student among the candidates at the top, so they can be easily removed. The comparison logic is:
    1.  Primary sort key: points, in ascending order (so lower points are "smaller").
    2.  Secondary sort key (for ties): student ID, in descending order (so higher IDs are "smaller").
*   **Step 4: Populate the Heap.** We iterate through each student and their calculated score. For each student, we add them to the heap. If the heap's size grows larger than `k`, we remove the top element using `poll()`, which discards the student with the lowest score (or highest ID in case of a tie) among the `k+1` students.
*   **Step 5: Extract and Order the Result.** After processing all students, the heap contains the top `k` students. However, they are ordered with the "worst" of the top `k` at the head. We need to extract them and reverse the order. We can repeatedly poll from the heap and add elements to the front of a result list (like a `LinkedList`) to get the final sorted list of student IDs.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> topStudents(String[] positive_feedback,
                            String[] negative_feedback, String[] report,
                            int[] student_id, int k) {
    Set<String> ps = new HashSet<>();
    Set<String> ns = new HashSet<>();
    for (var s : positive_feedback) {
      ps.add(s);
    }
    for (var s : negative_feedback) {
      ns.add(s);
    }
    int n = report.length;
    int[][] arr = new int[n][0];
    for (int i = 0; i < n; ++i) {
      int sid = student_id[i];
      int t = 0;
      for (var s : report[i].split(" ")) {
        if (ps.contains(s)) {
          t += 3;
        } else if (ns.contains(s)) {
          t -= 1;
        }
      }
      arr[i] = new int[]{t, sid};
    }
    Arrays.sort(arr, (a, b)->a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < k; ++i) {
      ans.add(arr[i][1]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> topStudents(vector<string> &positive_feedback,
                          vector<string> &negative_feedback,
                          vector<string> &report, vector<int> &student_id,
                          int k) {
    unordered_set<string> ps(positive_feedback.begin(),
                             positive_feedback.end());
    unordered_set<string> ns(negative_feedback.begin(),
                             negative_feedback.end());
    vector<pair<int, int>> arr;
    int n = report.size();
    for (int i = 0; i < n; ++i) {
      int sid = student_id[i];
      vector<string> ws = split(report[i], ' ');
      int t = 0;
      for (auto &w : ws) {
        if (ps.count(w)) {
          t += 3;
        } else if (ns.count(w)) {
          t -= 1;
        }
      }
      arr.push_back({-t, sid});
    }
    sort(arr.begin(), arr.end());
    vector<int> ans;
    for (int i = 0; i < k; ++i) {
      ans.emplace_back(arr[i].second);
    }
    return ans;
  }
  vector<string> split(string &s, char delim) {
    stringstream ss(s);
    string item;
    vector<string> res;
    while (getline(ss, item, delim)) {
      res.emplace_back(item);
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int, ) -> List[int]: ps = set(positive_feedback) ns = set(negative_feedback) arr = [] for sid, r in zip(student_id, report): t = 0 for w in r . split(): if w in ps: t += 3 elif w in ns: t -= 1 arr . append((t, sid)) arr . sort(key=lambda x: (- x[0], x[1])) return [v[1] for v in arr[: k]]

```