Watch 9 video solutions for Reward Top K Students, a medium level problem involving Array, Hash Table, String. This walkthrough by CodeWithSunny has 686 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |