LeetCode 2512 - Reward Top K Students

The problem asks us to compute a ranking of students based on textual feedback they receive. We are given two lists of words: positivefeedback and negativefeedback.

leetcodemediumarrayhash-tablestringsortingheap-(priority-queue)

LeetCode Problem 2512

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to compute a ranking of students based on textual feedback they receive. We are given two lists of words: positive_feedback and negative_feedback. Every time a student receives a report, we score that report by adding 3 points for each word that appears in positive_feedback and subtracting 1 point for each word that appears in negative_feedback. Each report is associated with a student via the student_id array. After processing all reports, we are asked to return the top k students ranked first by score in descending order, and in case of ties, by student ID in ascending order.

The inputs include:

  • positive_feedback and negative_feedback lists containing distinct words.
  • report, a list of strings, each representing a student report.
  • student_id, a list of integers representing the student ID corresponding to each report.
  • k, the number of top students to return.

Constraints indicate that the input size is moderate (n up to 10^4 and feedback word lists up to 10^4 words each), meaning the solution must be efficient in both time and space. Edge cases that could cause errors include reports with only positive or only negative words, multiple students with the same score, or words in the report not present in either feedback list.

Approaches

A brute-force approach would iterate over each report, split it into words, and for each word, check if it is in positive_feedback or negative_feedback. We then update a student's total score in a dictionary. After computing all scores, we would sort all students first by score descending, then by ID ascending, and take the first k students. This approach is correct but potentially slow because checking membership in a list has O(m) complexity, where m is the length of the feedback list, making the total complexity O(n * m * L) where L is the average number of words per report.

The optimal approach relies on converting the positive and negative feedback lists into sets, which allows O(1) membership checks. Then we iterate through each report, split it into words, compute the score efficiently using the sets, and maintain a mapping of student ID to cumulative score. Finally, we sort students based on a tuple of (-score, student_id) to achieve the required ranking and take the top k students. This reduces the membership check complexity drastically and keeps the solution within feasible time limits.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * L) O(n) List membership checks are slow for large feedback lists
Optimal O(n * L + m + p + n log n) O(n + m + p) Uses sets for O(1) lookups and sorts students by score and ID

Where m and p are the lengths of positive and negative feedback lists, n is the number of reports, and L is the average number of words per report.

Algorithm Walkthrough

  1. Convert positive_feedback and negative_feedback into sets positive_set and negative_set for fast membership lookup. This ensures O(1) time complexity per word check.
  2. Initialize an empty dictionary student_scores to track cumulative scores for each student.
  3. Iterate through each report and its corresponding student_id. For each report, split it into words.
  4. Initialize a score counter for the current report. For each word in the report, if the word is in positive_set, increment score by 3. If it is in negative_set, decrement score by 1. Words not in either set do not affect the score.
  5. Add the computed score to the cumulative score for the current student in student_scores.
  6. After processing all reports, create a list of tuples (student_id, score) from student_scores.
  7. Sort this list based on a key of (-score, student_id) so that higher scores come first and ties are broken by lower student IDs.
  8. Extract the first k student IDs from the sorted list and return them.

Why it works: The algorithm guarantees correctness because we compute each student's total points based strictly on the rules and sort by the exact criteria specified. The use of sets ensures efficient word lookups, and sorting ensures ties are correctly resolved by student ID.

Python Solution

from typing import List

class Solution:
    def topStudents(self, positive_feedback: List[str], negative_feedback: List[str], report: List[str], student_id: List[int], k: int) -> List[int]:
        positive_set = set(positive_feedback)
        negative_set = set(negative_feedback)
        
        student_scores = {}
        
        for sid, rep in zip(student_id, report):
            score = 0
            for word in rep.split():
                if word in positive_set:
                    score += 3
                elif word in negative_set:
                    score -= 1
            student_scores[sid] = student_scores.get(sid, 0) + score
        
        sorted_students = sorted(student_scores.items(), key=lambda x: (-x[1], x[0]))
        return [sid for sid, _ in sorted_students[:k]]

The code first constructs sets for fast word lookups, then iterates through each report and computes scores per student. The dictionary accumulates the score, and the final sort ensures students are ranked according to points with ties broken by student ID.

Go Solution

import (
    "sort"
    "strings"
)

func topStudents(positive_feedback []string, negative_feedback []string, report []string, student_id []int, k int) []int {
    positiveSet := make(map[string]struct{}, len(positive_feedback))
    negativeSet := make(map[string]struct{}, len(negative_feedback))
    
    for _, word := range positive_feedback {
        positiveSet[word] = struct{}{}
    }
    for _, word := range negative_feedback {
        negativeSet[word] = struct{}{}
    }
    
    studentScores := make(map[int]int)
    
    for i, rep := range report {
        score := 0
        words := strings.Fields(rep)
        for _, word := range words {
            if _, ok := positiveSet[word]; ok {
                score += 3
            } else if _, ok := negativeSet[word]; ok {
                score -= 1
            }
        }
        studentScores[student_id[i]] += score
    }
    
    type pair struct {
        id, score int
    }
    
    students := make([]pair, 0, len(studentScores))
    for id, score := range studentScores {
        students = append(students, pair{id, score})
    }
    
    sort.Slice(students, func(i, j int) bool {
        if students[i].score == students[j].score {
            return students[i].id < students[j].id
        }
        return students[i].score > students[j].score
    })
    
    res := make([]int, k)
    for i := 0; i < k; i++ {
        res[i] = students[i].id
    }
    return res
}

The Go version mirrors the Python logic. The key differences are handling slices versus lists, using maps with empty structs for sets, and using strings.Fields to split reports into words.

Worked Examples

Example 1

student_id report words score
1 "this student is studious" studious -> +3 3
2 "the student is smart" smart -> +3 3

Sorted by score and ID: [1, 2]

Example 2

student_id report words score
1 "this student is not studious" not -> -1, studious -> +3 2
2 "the student is smart" smart -> +3 3

Sorted by score and ID: [2, 1]

Complexity Analysis

Measure Complexity Explanation
Time O(n * L + m + p + n log n) L is average number of words per report, m and p are lengths of feedback lists, n log n for sorting students
Space O(n + m + p) O(n) for student scores, O(m + p) for sets of positive and negative feedback

We iterate once over each report and each word, do O(1) lookups in sets, then sort the students.

Test Cases

# Provided examples
assert Solution().topStudents(["smart","brilliant","studious"], ["not"], ["this student is studious","the student is smart"], [1,2], 2) == [1,2]  # equal score tie
assert Solution().topStudents(["smart","brilliant","studious"], ["not"], ["this student is not studious","the student is smart"], [1,2], 2) == [2,1]  # one higher score

# Single student, single report
assert Solution().topStudents(["good"], ["bad"], ["good good"], [10], 1) == [10]  # positive words count multiple times

# Negative words only
assert Solution().topStudents(["good"], ["bad"], ["bad bad bad"], [5], 1) == [5]  # negative scoring

# Mixed words
assert Solution().topStudents(["excellent"], ["poor