Introduction

In this blog post, we will explore how to solve the LeetCode problem "2512" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's the solution to the problem, focusing on efficiency and optimality:

• Core Idea: Calculate the score for each student based on their report and store it in a dictionary. Then, sort the students based on their scores and IDs to obtain the top k students.
• Efficient Data Structures: Use set for positive_feedback and negative_feedback for fast word lookup (O(1) on average). This avoids iterating through lists repeatedly. Use dictionary to store student scores.

• Optimized Sorting: Use Python's built-in sorted function with a custom lambda function for efficient sorting based on both score (descending) and student ID (ascending).

• Complexity:

  • Runtime: O(n*m + n*log(n)), where n is the number of reports and m is the average length of each report. The n*m comes from calculating the scores. n*log(n) comes from sorting the scores.
  • Storage: O(p + q + n), where p is the number of positive feedback words, q is the number of negative feedback words, and n is the number of students/reports.

Code

    def topStudents(positive_feedback: list[str], negative_feedback: list[str], report: list[str], student_id: list[int], k: int) -> list[int]:
    """
    Calculates the scores of students based on feedback reports and returns the top k students.

    Args:
        positive_feedback: List of positive feedback words.
        negative_feedback: List of negative feedback words.
        report: List of feedback reports.
        student_id: List of student IDs.
        k: Number of top students to return.

    Returns:
        List of top k student IDs.
    """

    positive_set = set(positive_feedback)
    negative_set = set(negative_feedback)

    student_scores = {}
    for i in range(len(report)):
        score = 0
        words = report[i].split()
        for word in words:
            if word in positive_set:
                score += 3
            elif word in negative_set:
                score -= 1
        student_scores[student_id[i]] = score

    sorted_students = sorted(student_scores.items(), key=lambda item: (-item[1], item[0]))  # Sort by score (descending) then ID (ascending)

    top_k_students = [student_id for student_id, score in sorted_students[:k]]
    return top_k_students