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 <= 100positive_feedback[i] and negative_feedback[j] consists of lowercase English letters.positive_feedback and negative_feedback.n == report.length == student_id.length1 <= n <= 104report[i] consists of lowercase English letters and spaces ' '.report[i].1 <= report[i].length <= 1001 <= student_id[i] <= 109student_id[i] are unique.1 <= k <= nProblem Overview: Each student submits a feedback report. Words in the report can increase or decrease the student's score depending on whether they appear in the positive or negative word lists. Your task is to compute every student's score, rank them by score (and by smaller student ID for ties), and return the top k student IDs.
The key idea is converting the positive and negative word lists into fast lookup structures, then computing a score for each report. After scores are calculated, the problem becomes a ranking task.
Approach 1: Dictionary with Sorting (O(n * m + n log n) time, O(n) space)
Store all positive and negative words in hash sets for constant-time membership checks. For each student's report, split the string into words and iterate through them. Add +3 for each positive word and subtract -1 for each negative word. Maintain a list of pairs (score, studentId). Once all scores are computed, sort the list by descending score and ascending student ID. The first k elements give the answer.
This approach relies heavily on hash table lookups and a final sorting step. It is straightforward and easy to implement in interviews. Time complexity comes from scanning all reports and sorting the resulting list of students.
Approach 2: Using Priority Queue (Heap) (O(n * m + n log k) time, O(n) space)
Score calculation is identical: convert positive and negative lists into hash sets and compute each student's score by iterating through their report words. Instead of sorting the entire list, maintain a min-heap of size k containing the best students seen so far. Each heap element stores (score, studentId) with custom ordering so the lowest-ranked candidate is removed when the heap exceeds size k.
This reduces the ranking cost when k is much smaller than n. Heap operations take O(log k), making the total ranking cost O(n log k). The approach uses a priority queue combined with string parsing for each report.
Recommended for interviews: The sorting approach is usually the first solution candidates write because it is simple and less error‑prone. Interviewers often accept it as a clean baseline. The heap approach demonstrates stronger algorithmic thinking because it optimizes ranking when only the top k results are required. Showing both indicates you understand both straightforward implementation and performance optimization.
This approach involves using a dictionary to map each student's ID to their computed score. We then sort this dictionary to determine the top K students. The sorting is based on two keys: the score (in descending order) and the student ID (in ascending order).
We use a combination of sets for quick lookup of positive and negative words. Loop through each report, splitting it into words, and update the score based on their presence in the feedback sets. Store the score against each student ID. Sort the students based on their score and ID, returning the top k students.
Time Complexity: O(n * m + n log n), where n is the number of reports, and m is the average number of words per report, as we parse each report, and sort it.
Space Complexity: O(n), where n is the number of unique student IDs.
In this approach, we utilize a heap (priority queue) to efficiently retrieve the top k students by their scores. We iterate over the reports to compute scores and store them in a min-heap. By maintaining the heap property, we ensure the complexity of retrieving the top k is reduced.
A priority queue (min-heap) is used where each score and student ID forms an entry. We compute the score from the report and push it into the heap. To ensure the heap does not exceed size k, elements are pushed and popped accordingly. In the end, the heap's contents are sorted and returned.
Python
JavaScript
Java
Time Complexity: O(n * m + k log n), for parsing and inserting into the heap.
Space Complexity: O(k), for storing the top k students in the heap.
We can store the positive words in a hash table ps and the negative words in a hash table ns.
Then, we traverse the report and for each student, we store their score in an array arr, where each element is a tuple (t, sid), where t represents the student's score and sid represents the student's ID.
Finally, we sort the array arr in descending order by score, and if the scores are the same, we sort by ID in ascending order. Then, we take the IDs of the top k students.
The time complexity is O(n times log n + (|ps| + |ns| + n) times |s|), and the space complexity is O((|ps|+|ns|) times |s| + n). Here, n is the number of students, |ps| and |ns| are the number of positive and negative words, respectively, and |s| is the average length of a word.
| Approach | Complexity |
|---|---|
| Approach 1: Dictionary with Sorting | Time Complexity: O(n * m + n log n), where n is the number of reports, and m is the average number of words per report, as we parse each report, and sort it. |
| Approach 2: Using Priority Queue (Heap) | Time Complexity: O(n * m + k log n), for parsing and inserting into the heap. |
| Hash Table + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dictionary with Sorting | O(n * m + n log n) | O(n) | Simple implementation when you need a full ranking of all students |
| Priority Queue (Heap) | O(n * m + n log k) | O(n) | Better when k is much smaller than n and only top results are required |
Reward Top K Students | 2512 LeetCode | Sortings | Leetcode Biweekly Contest 94 • CodeWithSunny • 686 views views
Watch 8 more video solutions →Practice Reward Top K Students with our built-in code editor and test cases.
Practice on FleetCode