Skip to main content
Talentd

Reward Top K Students - Solution & Explanation

MediumArrayHash TableStringSorting19 min readAsked at: Booking.com
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Approach 1: Dictionary with Sorting

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.

Code

PythonC++JavaScriptJavaC#C

Python

C++

JavaScript

Java

C#

C

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Using Priority Queue (Heap)

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.

Code

PythonJavaScriptJava

Python

JavaScript

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table + Sorting

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n), where n is the number of unique student IDs.

Approach 2: Using Priority Queue (Heap)

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.

Hash Table + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dictionary with SortingO(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

Video Solution

Reward Top K Students | 2512 LeetCode | Sortings | Leetcode Biweekly Contest 94 • CodeWithSunny • 688 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Reward Top K Students easy or hard?
Reward Top K Students is a Medium difficulty problem. The scoring logic is straightforward, but handling ranking with tie-breaking and choosing between sorting or a heap requires understanding of hash tables, string parsing, and top‑k selection techniques.
How to solve Reward Top K Students in O(n log k)?
Calculate scores for each student using hash set lookups for positive and negative words. Maintain a min-heap of size k storing the best students. Each time a new score is computed, push it into the heap and remove the smallest if the size exceeds k. Heap operations cost O(log k), giving total complexity O(n log k) after scoring.
What is the best approach for Reward Top K Students?
The most practical approach computes each student's score using hash sets for positive and negative words, then ranks students. A full sort gives O(n log n) time and is easiest to implement. When k is much smaller than n, a min-heap keeps only the top k students and reduces ranking time to O(n log k).
Is Reward Top K Students asked at Google/Amazon/Meta?
Problems involving ranking with heaps and scoring with hash tables frequently appear in interviews at large tech companies such as Amazon, Google, and Meta. The combination of string processing, hash lookups, and top‑k selection mirrors many real interview questions.
What data structure is used in Reward Top K Students?
The solution primarily uses hash sets (or hash tables) to store positive and negative words for O(1) lookup. A sorting algorithm or a priority queue (heap) is then used to rank students by score. Arrays or lists store the intermediate score and student ID pairs.
What is the time complexity of Reward Top K Students?
Computing scores requires scanning every report word, which takes O(n * m) where m is the average number of words per report. If you sort all students, the total complexity becomes O(n * m + n log n). Using a heap for the top k students improves the ranking step to O(n log k).
Reward Top K Students Python or Java solution approach?
In both Python and Java, store positive and negative words in hash sets, split each report into words, and compute the score. After that, either sort the list of (score, studentId) pairs or maintain a priority queue to track the top k students.

Ready to solve this problem?

Practice Reward Top K Students with our built-in code editor and test cases.

Practice on FleetCode
Previous

K Highest Ranked Items Within a Price Range

Next

Queue Reconstruction by Height