#2512

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Reward Top K Students

Calculate top K student scores by scanning reports and using hash tables for positive and negative word lookups efficiently.

array hash table string sorting heap priority queue

Problem Statement

You are given two string arrays, positive_feedback and negative_feedback, containing words representing good or bad feedback. Each student starts with 0 points, gaining 3 points for each positive word and losing 1 point for each negative word in their reports.

You are also given n feedback reports in a string array report and a corresponding integer array student_id where student_id[i] identifies the student for report[i]. Your task is to determine the IDs of the top K students based on total points, resolving ties by selecting the student with the smaller ID first.

Examples

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]

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]

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

Solution Approach

Hash feedback words for fast lookup

Store positive_feedback and negative_feedback words in separate hash sets. This allows constant time checks while scanning report words, minimizing redundant searches and improving overall runtime.

Compute scores by scanning reports

For each report[i], split the report into words and update the corresponding student's score using the hash sets. Increment by 3 for positive words and decrement by 1 for negative words, accumulating totals in a map keyed by student ID.

Sort students and select top K

After calculating all scores, convert the map to a list of tuples (score, student_id) and sort descending by score and ascending by ID. Select the first K entries to produce the result list of top students.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * m) where n is number of reports and m is average words per report, plus O(n log n) for sorting. Space complexity is O(p + q + n) for positive/negative sets and storing scores.

What Interviewers Usually Probe

Checks if you use hash sets for feedback words instead of repeated list searches.
Looks for splitting each report efficiently and tallying scores correctly.
Validates sorting by score and breaking ties using student IDs.

Common Pitfalls or Variants

Common pitfalls

Forgetting to hash the feedback words causes slower lookups and possible timeouts.
Incorrectly handling ties by student ID can produce wrong top K ordering.
Failing to split report words correctly, miscounting points due to punctuation or spaces.

Follow-up variants

Return bottom K students instead of top K using same scoring mechanism.
Use weighted positive and negative points for different words.
Handle multiple reports per student with aggregation and weighted scoring.

FAQ

How are points calculated in Reward Top K Students?

Each positive word in a report adds 3 points, and each negative word subtracts 1 point from the corresponding student's total.

Why use hash sets for positive and negative feedback words?

Hash sets allow O(1) lookup per word, ensuring scanning each report is efficient without repeatedly searching lists.

How do I resolve ties when students have the same score?

Sort students by score descending, then by student ID ascending. Lower ID wins when points are equal.

What is the primary pattern in solving this problem?

The main pattern is array scanning plus hash lookup: scan reports and check words using hash sets for scoring.

Can a student appear in multiple reports?

Yes, scores from all reports for the same student are accumulated before determining the top K students.

terminal

Solution

Solution 1: Hash Table + Sorting

We can store the positive words in a hash table $ps$ and the negative words in a hash table $ns$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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]]

Continue Practicing