Reward Top K Students
MedPrompt
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 <= 1041 <= positive_feedback[i].length, negative_feedback[j].length <= 100- Both
positive_feedback[i]andnegative_feedback[j]consists of lowercase English letters. - No word is present in both
positive_feedbackandnegative_feedback. n == report.length == student_id.length1 <= n <= 104report[i]consists of lowercase English letters and spaces' '.- There is a single space between consecutive words of
report[i]. 1 <= report[i].length <= 1001 <= student_id[i] <= 109- All the values of
student_id[i]are unique. 1 <= k <= n
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Step 1: Pre-process Feedback Words. To allow for efficient lookups, we store the
positive_feedbackandnegative_feedbackwords 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
reportarray. 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
kstudents are simply the firstkelements in the list. We extract their IDs and return them as the result.
Walkthrough
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; }}Complexity
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.
Trade-offs
Pros
Relatively simple to understand and implement.
Uses standard library functions for sorting.
Cons
Sorting all
Sstudents is inefficient ifkis much smaller thanS. The complexity isO(S log S)regardless ofk.
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.
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
PriorityQueuein Java) with a maximum size ofk. 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:- Primary sort key: points, in ascending order (so lower points are "smaller").
- 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 usingpoll(), which discards the student with the lowest score (or highest ID in case of a tie) among thek+1students. - Step 5: Extract and Order the Result. After processing all students, the heap contains the top
kstudents. However, they are ordered with the "worst" of the topkat 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 aLinkedList) to get the final sorted list of student IDs.
Walkthrough
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; }}Complexity
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.
Trade-offs
Pros
More efficient than full sorting, with a time complexity of
O(S log k)for the selection part.Ideal for scenarios where
kis 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.
Solutions
Solution
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; }}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; }};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]]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.