Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2512.html

2512. Reward Top K Students

Description

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

Solutions

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$.

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.
  • class Solution {
        public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback,
            String[] report, int[] student_id, int k) {
            Set<String> ps = new HashSet<>();
            Set<String> ns = new HashSet<>();
            for (var s : positive_feedback) {
                ps.add(s);
            }
            for (var s : negative_feedback) {
                ns.add(s);
            }
            int n = report.length;
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; ++i) {
                int sid = student_id[i];
                int t = 0;
                for (var s : report[i].split(" ")) {
                    if (ps.contains(s)) {
                        t += 3;
                    } else if (ns.contains(s)) {
                        t -= 1;
                    }
                }
                arr[i] = new int[] {t, sid};
            }
            Arrays.sort(arr, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
            List<Integer> ans = new ArrayList<>();
            for (int i = 0; i < k; ++i) {
                ans.add(arr[i][1]);
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        vector<int> topStudents(vector<string>& positive_feedback, vector<string>& negative_feedback, vector<string>& report, vector<int>& student_id, int k) {
            unordered_set<string> ps(positive_feedback.begin(), positive_feedback.end());
            unordered_set<string> ns(negative_feedback.begin(), negative_feedback.end());
            vector<pair<int, int>> arr;
            int n = report.size();
            for (int i = 0; i < n; ++i) {
                int sid = student_id[i];
                vector<string> ws = split(report[i], ' ');
                int t = 0;
                for (auto& w : ws) {
                    if (ps.count(w)) {
                        t += 3;
                    } else if (ns.count(w)) {
                        t -= 1;
                    }
                }
                arr.push_back({-t, sid});
            }
            sort(arr.begin(), arr.end());
            vector<int> ans;
            for (int i = 0; i < k; ++i) {
                ans.emplace_back(arr[i].second);
            }
            return ans;
        }
    
        vector<string> split(string& s, char delim) {
            stringstream ss(s);
            string item;
            vector<string> res;
            while (getline(ss, item, delim)) {
                res.emplace_back(item);
            }
            return res;
        }
    };
    
  • 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]]
    
    
  • 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
    }
    
  • 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);
    }
    
    
  • 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()
        }
    }
    
    

All Problems

All Solutions