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 topk students after ranking them innon-increasing order by their points. In case more than one student has the same points, the one with the lower ID ranks higher.

Examples

Example 1

1
2
3
4

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

1
2
3
4
5
6

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 <= 10^4
  • 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 <= 10^4
  • 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] <= 10^9
  • All the values of student_id[i] are unique.
  • 1 <= k <= n

Solution

Method 1 - Hash Set and Sorting

Intuition

We need to efficiently check if a word is positive or negative, so we use sets for O(1) lookup. For each report, count the score for each student, then sort by score (descending) and student ID (ascending).

Approach

Build sets for positive and negative feedback. For each report, split into words and update the student’s score. Collect all (score, student_id) pairs, sort by score descending and student_id ascending, and return the top k student IDs.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <algorithm>
using namespace std;
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> pos(positive_feedback.begin(), positive_feedback.end());
        unordered_set<string> neg(negative_feedback.begin(), negative_feedback.end());
        unordered_map<int, int> score;
        int n = report.size();
        for (int i = 0; i < n; ++i) {
            int s = 0;
            istringstream iss(report[i]);
            string word;
            while (iss >> word) {
                if (pos.count(word)) s += 3;
                else if (neg.count(word)) s -= 1;
            }
            score[student_id[i]] = s;
        }
        vector<pair<int, int>> v;
        for (auto& [id, s] : score) v.emplace_back(-s, id); // -s for descending
        sort(v.begin(), v.end());
        vector<int> res;
        for (int i = 0; i < k; ++i) res.push_back(v[i].second);
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import (
    "strings"
    "sort"
)
func topStudents(positive_feedback, negative_feedback, report []string, student_id []int, k int) []int {
    pos := make(map[string]bool)
    for _, w := range positive_feedback { pos[w] = true }
    neg := make(map[string]bool)
    for _, w := range negative_feedback { neg[w] = true }
    score := make(map[int]int)
    for i, rep := range report {
        s := 0
        for _, word := range strings.Fields(rep) {
            if pos[word] { s += 3 }
            if neg[word] { s -= 1 }
        }
        score[student_id[i]] = s
    }
    type pair struct{score, id int}
    v := make([]pair, 0, len(score))
    for id, s := range score { v = append(v, pair{-s, id}) }
    sort.Slice(v, func(i, j int) bool {
        if v[i].score != v[j].score { return v[i].score < v[j].score }
        return v[i].id < v[j].id
    })
    res := make([]int, k)
    for i := 0; i < k; i++ { res[i] = v[i].id }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public List<Integer> topStudents(List<String> positive_feedback, List<String> negative_feedback, List<String> report, List<Integer> student_id, int k) {
        Set<String> pos = new HashSet<>(positive_feedback);
        Set<String> neg = new HashSet<>(negative_feedback);
        Map<Integer, Integer> score = new HashMap<>();
        for (int i = 0; i < report.size(); i++) {
            int s = 0;
            for (String word : report.get(i).split(" ")) {
                if (pos.contains(word)) s += 3;
                if (neg.contains(word)) s -= 1;
            }
            score.put(student_id.get(i), s);
        }
        List<int[]> v = new ArrayList<>();
        for (var e : score.entrySet()) v.add(new int[]{-e.getValue(), e.getKey()});
        v.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) res.add(v.get(i)[1]);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun topStudents(positive_feedback: List<String>, negative_feedback: List<String>, report: List<String>, student_id: List<Int>, k: Int): List<Int> {
        val pos = positive_feedback.toSet()
        val neg = negative_feedback.toSet()
        val score = mutableMapOf<Int, Int>()
        for (i in report.indices) {
            var s = 0
            for (word in report[i].split(" ")) {
                if (word in pos) s += 3
                if (word in neg) s -= 1
            }
            score[student_id[i]] = s
        }
        val v = score.map { (-it.value) to it.key }.toMutableList()
        v.sortWith(compareBy({ it.first }, { it.second }))
        return v.take(k).map { it.second }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def topStudents(self, positive_feedback, negative_feedback, report, student_id, k):
        pos = set(positive_feedback)
        neg = set(negative_feedback)
        score = {}
        for rep, sid in zip(report, student_id):
            s = 0
            for word in rep.split():
                if word in pos:
                    s += 3
                if word in neg:
                    s -= 1
            score[sid] = s
        v = [(-s, sid) for sid, s in score.items()]
        v.sort()
        return [sid for _, sid in v[:k]]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

use std::collections::{HashSet, HashMap};
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 pos: HashSet<_> = positive_feedback.into_iter().collect();
        let neg: HashSet<_> = negative_feedback.into_iter().collect();
        let mut score = HashMap::new();
        for (rep, sid) in report.iter().zip(student_id.iter()) {
            let mut s = 0;
            for word in rep.split_whitespace() {
                if pos.contains(word) { s += 3; }
                if neg.contains(word) { s -= 1; }
            }
            score.insert(*sid, s);
        }
        let mut v: Vec<(i32, i32)> = score.into_iter().map(|(sid, s)| (-s, sid)).collect();
        v.sort();
        v.into_iter().take(k as usize).map(|(_, sid)| sid).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

function topStudents(positive_feedback: string[], negative_feedback: string[], report: string[], student_id: number[], k: number): number[] {
    const pos = new Set(positive_feedback);
    const neg = new Set(negative_feedback);
    const score = new Map<number, number>();
    for (let i = 0; i < report.length; i++) {
        let s = 0;
        for (const word of report[i].split(' ')) {
            if (pos.has(word)) s += 3;
            if (neg.has(word)) s -= 1;
        }
        score.set(student_id[i], s);
    }
    const v: [number, number][] = [];
    for (const [sid, s] of score.entries()) v.push([-s, sid]);
    v.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    return v.slice(0, k).map(x => x[1]);
}

Complexity

  • ⏰ Time complexity: O(N + M + L + n log n) — where N, M are the lengths of positive/negative_feedback, L is the total number of words in all reports, and n is the number of students (for sorting).
  • 🧺 Space complexity: O(N + M + n) — for sets and score map.