Reward Top K Students solution and explanation
8 more videos on this problem
Reward Top K Students | 2512 LeetCode | Sortings | Leetcode Biweekly Contest 94CodeWithSunny · 7:40 · 688 views
Leetcode BiWeekly contest 94 - Medium - Reward Top K StudentsPrakhar Agrawal · 7:21 · 530 views
2512. Reward Top K Students (Leetcode Medium)Programming Live with Larry · 6:49 · 369 views
LeetCode 2512: Reward Top K Students | Easy Intuition + Optimal CodeGirish Thatte · 12:23 · 363 views
Leetcode 2512 Reward Top K StudentsAlgorithmicIQ · 18:10 · 285 views
LeetCode 2512. Reward Top K Students | Simple Explanation with CodeDeep Tech · 13:02 · 170 views
Leecode Biweekly Contest 94 | 2511.Max Enemy Forts That Can Be Captured| 2512.Reward Top K StudentsCodingVerse · 14:18 · 79 views
LeetCode (Biweekly Contest) | Reward Top K Students | Proper Explanation & CodeDivyam Kakkar - LevelUp Coding · 17:34 · 72 views
Rewarding Top K Students, In Depth Problem Explanation LeetCode Problem Medium 2512💡Talent Navigator · 15:59 · 1 view
The 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 <= 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
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).
def topStudents(positive_feedback, negative_feedback, report, student_id, k):
from collections import defaultdict
pos_set = set(positive_feedback)
neg_set = set(negative_feedback)
scores = defaultdict(int)
for i in range(len(report)):
score = 0
words = report[i].split()
for word in words:
if word in pos_set:
score += 3
elif word in neg_set:
score -= 1
scores[student_id[i]] += score
sorted_students = sorted(scores.keys(), key=lambda x: (-scores[x], x))
return sorted_students[:k]import java.util.*;
public class TopStudents {
public static List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
Set<String> posSet = new HashSet<>(Arrays.asList(positive_feedback));
Set<String> negSet = new HashSet<>(Arrays.asList(negative_feedback));
Map<Integer, Integer> scores = new HashMap<>();
for (int i = 0; i < report.length; i++) {
String[] words = report[i].split(" ");
int score = 0;
for (String word : words) {
if (posSet.contains(word)) score += 3;
if (negSet.contains(word)) score -= 1;
}
scores.put(student_id[i], scores.getOrDefault(student_id[i], 0) + score);
}
return scores.entrySet().stream()
.sorted((a, b) -> b.getValue().equals(a.getValue()) ? Integer.compare(a.getKey(), b.getKey()) : Integer.compare(b.getValue(), a.getValue()))
.limit(k)
.map(Map.Entry::getKey)
.collect(Collectors.toList());
}
}#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
std::vector<int> topStudents(std::vector<std::string>& positive_feedback, std::vector<std::string>& negative_feedback, std::vector<std::string>& report, std::vector<int>& student_id, int k) {
std::unordered_set<std::string> pos_set(positive_feedback.begin(), positive_feedback.end());
std::unordered_set<std::string> neg_set(negative_feedback.begin(), negative_feedback.end());
std::unordered_map<int, int> scores;
for (int i = 0; i < report.size(); ++i) {
int score = 0;
std::istringstream iss(report[i]);
std::string word;
while (iss >> word) {
if (pos_set.count(word) > 0) score += 3;
if (neg_set.count(word) > 0) score -= 1;
}
scores[student_id[i]] += score;
}
std::vector<std::pair<int, int>> sorted_scores;
for (auto& pair : scores) {
sorted_scores.push_back(pair);
}
std::sort(sorted_scores.begin(), sorted_scores.end(), [](const auto& a, const auto& b) {
return a.second > b.second || (a.second == b.second && a.first < b.first);
});
std::vector<int> result;
for (int i = 0; i < k; ++i) {
result.push_back(sorted_scores[i].first);
}
return result;
}function topStudents(positive_feedback, negative_feedback, report, student_id, k) {
const posSet = new Set(positive_feedback);
const negSet = new Set(negative_feedback);
const scores = new Map();
for (let i = 0; i < report.length; i++) {
const words = report[i].split(' ');
let score = 0;
for (const word of words) {
if (posSet.has(word)) {
score += 3;
} else if (negSet.has(word)) {
score -= 1;
}
}
scores.set(student_id[i], (scores.get(student_id[i]) || 0) + score);
}
return Array.from(scores).sort((a, b) => b[1] - a[1] || a[0] - b[0]).slice(0, k).map(el => el[0]);
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// comparing function
int cmp(const void *a, const void *b) {
int *p1 = *(int **)a;
int *p2 = *(int **)b;
if (p1[1] != p2[1]) return p2[1] - p1[1]; // descending score
return p1[0] - p2[0]; // ascending student ID
}
// function to find the index in a set
int findIndex(char **set, int size, char *word) {
for (int i = 0; i < size; i++) {
if (strcmp(set[i], word) == 0) return i;
}
return -1;
}
void topStudents(char **positive_feedback, int pos_size, char **negative_feedback, int neg_size, char **report, int *student_id, int n, int k, int *result) {
int **scores = malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
scores[i] = malloc(2 * sizeof(int));
scores[i][0] = student_id[i];
scores[i][1] = 0;
char *token = strtok(report[i], " ");
while (token != NULL) {
if (findIndex(positive_feedback, pos_size, token) != -1) scores[i][1] += 3;
if (findIndex(negative_feedback, neg_size, token) != -1) scores[i][1] -= 1;
token = strtok(NULL, " ");
}
}
qsort(scores, n, sizeof(scores[0]), cmp);
for (int i = 0; i < k; i++) {
result[i] = scores[i][0];
}
for (int i = 0; i < n; i++) {
free(scores[i]);
}
free(scores);
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public List<int> TopStudents(string[] positive_feedback, string[] negative_feedback, string[] report, int[] student_id, int k) {
HashSet<string> posSet = new HashSet<string>(positive_feedback);
HashSet<string> negSet = new HashSet<string>(negative_feedback);
Dictionary<int, int> scores = new Dictionary<int, int>();
for (int i = 0; i < report.Length; i++) {
int score = 0;
string[] words = report[i].Split(' ');
foreach (string word in words) {
if (posSet.Contains(word)) score += 3;
if (negSet.Contains(word)) score -= 1;
}
if (!scores.ContainsKey(student_id[i])) {
scores[student_id[i]] = 0;
}
scores[student_id[i]] += score;
}
return scores.OrderByDescending(x => x.Value)
.ThenBy(x => x.Key)
.Take(k)
.Select(x => x.Key)
.ToList();
}
}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.
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.
import heapq
def topStudents(positive_feedback, negative_feedback, report, student_id, k):
pos_set = set(positive_feedback)
neg_set = set(negative_feedback)
scores = {}
for i in range(len(report)):
score = 0
words = report[i].split()
for word in words:
if word in pos_set:
score += 3
elif word in neg_set:
score -= 1
scores[student_id[i]] = scores.get(student_id[i], 0) + score
min_heap = []
for sid, score in scores.items():
heapq.heappush(min_heap, (score, sid))
if len(min_heap) > k:
heapq.heappop(min_heap)
result = sorted(min_heap, key=lambda x: (-x[0], x[1]))
return [sid for score, sid in result]import java.util.*;
public class TopStudentsPriorityQueue {
public static List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
Set<String> posSet = new HashSet<>(Arrays.asList(positive_feedback));
Set<String> negSet = new HashSet<>(Arrays.asList(negative_feedback));
Map<Integer, Integer> scores = new HashMap<>();
for (int i = 0; i < report.length; i++) {
String[] words = report[i].split(" ");
int score = 0;
for (String word : words) {
if (posSet.contains(word)) score += 3;
if (negSet.contains(word)) score -= 1;
}
scores.put(student_id[i], scores.getOrDefault(student_id[i], 0) + score);
}
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
for (Map.Entry<Integer, Integer> entry : scores.entrySet()) {
minHeap.offer(new int[] {entry.getValue(), entry.getKey()});
if (minHeap.size() > k) {
minHeap.poll();
}
}
List<Integer> result = new ArrayList<>();
while (!minHeap.isEmpty()) {
result.add(minHeap.poll()[1]);
}
Collections.reverse(result);
return result;
}
}function topStudents(positive_feedback, negative_feedback, report, student_id, k) {
const posSet = new Set(positive_feedback);
const negSet = new Set(negative_feedback);
const scores = new Map();
for (let i = 0; i < report.length; i++) {
const words = report[i].split(' ');
let score = 0;
for (const word of words) {
if (posSet.has(word)) {
score += 3;
} else if (negSet.has(word)) {
score -= 1;
}
}
scores.set(student_id[i], (scores.get(student_id[i]) || 0) + score);
}
let heap = [];
for (const [sid, score] of scores.entries()) {
heap.push([score, sid]);
heap.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
if (heap.length > k) heap.shift();
}
return heap.sort((a, b) => b[0] - a[0] || a[1] - b[1]).map(el => el[1]);
}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.
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.
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.
function topStudents(
positive_feedback: string[],
negative_feedback: string[],
report: string[],
student_id: number[],
k: number,
): number[] {
const n = student_id.length;
const map = new Map<number, number>();
const ps = new Set(positive_feedback);
const ns = new Set(negative_feedback);
for (let i = 0; i < n; i++) {
map.set(
student_id[i],
report[i].split(' ').reduce((r, s) => {
if (ps.has(s)) {
return r + 3;
}
if (ns.has(s)) {
return r - 1;
}
return r;
}, 0),
);
}
return [...map.entries()]
.sort((a, b) => {
if (a[1] === b[1]) {
return a[0] - b[0];
}
return b[1] - a[1];
})
.map(v => v[0])
.slice(0, k);
}func topStudents(positive_feedback []string, negative_feedback []string, report []string, student_id []int, k int) (ans []int) {
ps := map[string]bool{}
ns := map[string]bool{}
for _, s := range positive_feedback {
ps[s] = true
}
for _, s := range negative_feedback {
ns[s] = true
}
arr := [][2]int{}
for i, sid := range student_id {
t := 0
for _, w := range strings.Split(report[i], " ") {
if ps[w] {
t += 3
} else if ns[w] {
t -= 1
}
}
arr = append(arr, [2]int{t, sid})
}
sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] || (arr[i][0] == arr[j][0] && arr[i][1] < arr[j][1]) })
for _, v := range arr[:k] {
ans = append(ans, v[1])
}
return
}use std::collections::{HashMap, HashSet};
impl Solution {
pub fn top_students(
positive_feedback: Vec<String>,
negative_feedback: Vec<String>,
report: Vec<String>,
student_id: Vec<i32>,
k: i32,
) -> Vec<i32> {
let n = student_id.len();
let ps = positive_feedback.iter().collect::<HashSet<&String>>();
let ns = negative_feedback.iter().collect::<HashSet<&String>>();
let mut map = HashMap::new();
for i in 0..n {
let id = student_id[i];
let mut count = 0;
for s in report[i].split(' ') {
let s = &s.to_string();
if ps.contains(s) {
count += 3;
} else if ns.contains(s) {
count -= 1;
}
}
map.insert(id, count);
}
let mut t = map.into_iter().collect::<Vec<(i32, i32)>>();
t.sort_by(|a, b| {
if a.1 == b.1 {
return a.0.cmp(&b.0);
}
b.1.cmp(&a.1)
});
t.iter().map(|v| v.0).collect::<Vec<i32>>()[0..k as usize].to_vec()
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
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.