Problem Description

You need to rank students based on feedback reports containing positive and negative words.

Input:

• positive_feedback: An array of strings representing positive words
• negative_feedback: An array of strings representing negative words (no word appears in both arrays)
• report: An array of strings where each string is a feedback report for a student
• student_id: An array of integers where student_id[i] is the ID of the student who received report[i]
• k: An integer representing how many top students to return

Scoring Rules:

• Each student starts with 0 points
• Each positive word in their feedback report adds 3 points
• Each negative word in their feedback report subtracts 1 point

Task: Return the IDs of the top k students ranked by:

1. Points in descending order (highest points first)
2. If points are equal, rank by student ID in ascending order (lower ID ranks higher)

Example: If a student's report contains "good excellent bad", and "good" and "excellent" are positive words while "bad" is negative, the student would score: 3 + 3 - 1 = 5 points.

The solution uses hash sets to store positive and negative words for O(1) lookup, calculates each student's score by parsing their report, stores the results as (score, student_id) tuples, sorts them according to the ranking criteria, and returns the top k student IDs.

Intuition

The problem asks us to rank students based on their feedback scores, so we need to:

1. Calculate each student's score efficiently: Since we need to check if each word in a report is positive or negative, using hash sets for positive_feedback and negative_feedback gives us O(1) lookup time per word. This is much better than searching through arrays which would take O(n) time for each word.

2. Process multiple reports: We need to go through each student's report, split it into individual words, and check each word against our positive and negative word sets. For each word match, we update the running score accordingly (+3 for positive, -1 for negative).

3. Handle the ranking criteria: The problem has a two-level sorting requirement:

   • Primary: Sort by points (highest first)
   • Secondary: Sort by student ID (lowest first) when points are equal

   We can achieve this by storing each student's data as a tuple (score, student_id) and using a custom sort key. By sorting with (-score, student_id), we get descending order for scores (the negative sign reverses the order) and ascending order for IDs.

4. Return top k students: After sorting all students according to the ranking criteria, we simply take the first k elements and extract their student IDs.

The key insight is that we don't need complex data structures - just efficient lookups for word checking (hash sets), a simple way to store score-ID pairs (tuples), and Python's built-in sorting with a custom key function to handle the ranking rules.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution follows these implementation steps:

1. Create Hash Sets for Word Lookup

   ps = set(positive_feedback)
   ns = set(negative_feedback)

   Convert both feedback arrays into sets for O(1) lookup time when checking if a word is positive or negative.

2. Calculate Scores for Each Student

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

   • Use zip() to iterate through student IDs and their corresponding reports simultaneously
   • For each report, split it into individual words using split()
   • Check each word against the positive and negative sets
   • Accumulate the score t: add 3 for positive words, subtract 1 for negative words
   • Store the result as a tuple (score, student_id) in the array arr

3. Sort Students by Ranking Criteria

   arr.sort(key=lambda x: (-x[0], x[1]))

   Sort the array using a custom key function:

   • -x[0]: Negative score ensures descending order (highest scores first)
   • x[1]: Student ID in ascending order (lower IDs rank higher for equal scores)

4. Extract Top k Student IDs

   return [v[1] for v in arr[:k]]

   • Slice the first k elements from the sorted array
   • Use list comprehension to extract only the student IDs (index 1 of each tuple)
   • Return the resulting list of top k student IDs

The time complexity is O(n × m + n log n) where n is the number of students and m is the average number of words per report. The space complexity is O(p + q + n) where p and q are the sizes of positive and negative feedback arrays.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach:

Given:

• positive_feedback = ["smart", "brilliant", "studious"]
• negative_feedback = ["lazy", "slow"]
• report = ["this student is brilliant and smart", "lazy but studious", "slow learner"]
• student_id = [1, 5, 2]
• k = 2

Step 1: Create Hash Sets

ps = {smart, brilliant, studious}
ns = {lazy, slow}

Step 2: Calculate Scores for Each Student

Student 1 (report: "this student is brilliant and smart"):

• "this" → not in ps or ns → score: 0
• "student" → not in ps or ns → score: 0
• "is" → not in ps or ns → score: 0
• "brilliant" → in ps → score: 0 + 3 = 3
• "and" → not in ps or ns → score: 3
• "smart" → in ps → score: 3 + 3 = 6
• Store: (6, 1)

Student 5 (report: "lazy but studious"):

• "lazy" → in ns → score: 0 - 1 = -1
• "but" → not in ps or ns → score: -1
• "studious" → in ps → score: -1 + 3 = 2
• Store: (2, 5)

Student 2 (report: "slow learner"):

• "slow" → in ns → score: 0 - 1 = -1
• "learner" → not in ps or ns → score: -1
• Store: (-1, 2)

Array after scoring: arr = [(6, 1), (2, 5), (-1, 2)]

Step 3: Sort by Ranking Criteria

Apply sorting with key (-score, student_id):

• (6, 1) → key: (-6, 1)
• (2, 5) → key: (-2, 5)
• (-1, 2) → key: (1, 2)

Sorted order: [(6, 1), (2, 5), (-1, 2)]

Step 4: Extract Top k=2 Student IDs

Take first 2 elements: [(6, 1), (2, 5)] Extract IDs: [1, 5]

Final Answer: [1, 5]

The top 2 students are Student 1 (6 points) and Student 5 (2 points).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + n × m)

• Converting positive_feedback and negative_feedback to sets takes O(|ps| × |s| + |ns| × |s|) where |ps| is the number of positive words, |ns| is the number of negative words, and |s| is the average length of a word.
• The main loop iterates through n students, and for each student:
  • Splitting the report string takes O(m) where m is the number of words in the report
  • Checking each word against the sets takes O(|s|) per word (hash set lookup), so O(m × |s|) total per student
  • Overall for all students: O(n × m × |s|)
• Sorting the array of n students takes O(n × log n)
• Creating the final result list takes O(k) where k ≤ n

Combined: O((|ps| + |ns|) × |s| + n × m × |s| + n × log n), which simplifies to O(n × log n + (|ps| + |ns| + n × m) × |s|). When considering m as part of the total words across all reports (making it equivalent to n in terms of total processing), this becomes O(n × log n + (|ps| + |ns| + n) × |s|).

Space Complexity: O((|ps| + |ns|) × |s| + n)

• The sets ps and ns store all positive and negative words: O((|ps| + |ns|) × |s|)
• The arr list stores tuples for n students: O(n)
• The split operation creates temporary lists but only one at a time: O(m) which is dominated by other terms
• The final result list stores at most k student IDs: O(k) where k ≤ n

Combined: O((|ps| + |ns|) × |s| + n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Word Boundary Issues with Substring Matching

A critical mistake is checking if positive/negative words are substrings of the report rather than exact word matches:

Incorrect Approach:

# Wrong - this checks for substrings
for word in positive_feedback:
    if word in report[i]:  # This matches "good" in "goodness"
        score += 3

Why it's wrong: If "good" is a positive word and the report contains "goodness", this would incorrectly add 3 points since "good" is a substring of "goodness".

Correct Solution:

# Split the report into individual words first
for word in student_report.split():
    if word in positive_words:
        score += 3

2. Incorrect Sorting Order

Mixing up the sorting criteria is a frequent error:

Incorrect Approach:

# Wrong - sorts scores in ascending order
student_scores.sort(key=lambda x: (x[0], x[1]))
# Or wrong - sorts IDs in descending order for ties
student_scores.sort(key=lambda x: (-x[0], -x[1]))

Correct Solution:

# Scores descending (highest first), IDs ascending (lowest first for ties)
student_scores.sort(key=lambda x: (-x[0], x[1]))

3. Case Sensitivity Issues

The problem doesn't specify case handling, but assuming case-sensitive matching when it should be case-insensitive (or vice versa) can cause errors:

Potential Issue:

# If "Good" in report but "good" in positive_feedback
if word in positive_words:  # Won't match due to case difference

Solution if case-insensitive matching is needed:

# Convert everything to lowercase
positive_words = set(word.lower() for word in positive_feedback)
negative_words = set(word.lower() for word in negative_feedback)

for word in student_report.split():
    word_lower = word.lower()
    if word_lower in positive_words:
        score += 3
    elif word_lower in negative_words:
        score -= 1

4. Not Handling Edge Cases

Failing to consider edge cases like empty reports or k larger than the number of students:

Potential Issues:

• Empty report strings that cause unexpected behavior
• k > len(student_id) causing index errors

Robust Solution:

# Handle empty reports gracefully
for word in student_report.split():  # split() on empty string returns []
    # Process normally
  
# Handle k larger than number of students
return [student_info[1] for student_info in student_scores[:min(k, len(student_scores))]]

5. Using Lists Instead of Sets for Lookup

Using the original lists for word lookup instead of converting to sets:

Incorrect (Inefficient) Approach:

# O(n) lookup time for each word check
if word in positive_feedback:  # positive_feedback is a list
    score += 3

Correct Solution:

# O(1) lookup time with sets
positive_words = set(positive_feedback)
if word in positive_words:
    score += 3

This increases time complexity from O(n × m × p) to O(n × m) where p is the size of the feedback arrays.