Find Top Scoring Students II

Problem

Table: students

+-------------+----------+
| Column Name | Type     |
+-------------+----------+
| student_id  | int      |
| name        | varchar  |
| major       | varchar  |
+-------------+----------+
student_id is the primary key for this table.
Each row contains the student ID, student name, and their major.

Table: courses

+-------------+-------------------+
| Column Name | Type              |
+-------------+-------------------+
| course_id   | int               |
| name        | varchar           |
| credits     | int               |
| major       | varchar           |
| mandatory   | enum              |
+-------------+-------------------+
course_id is the primary key for this table.
mandatory is an enum type of ('Yes', 'No').
Each row contains the course ID, course name, credits, major it belongs to, and whether the course is mandatory.

Table: enrollments

+-------------+----------+
| Column Name | Type     |
+-------------+----------+
| student_id  | int      |
| course_id   | int      |
| semester    | varchar  |
| grade       | varchar  |
| GPA         | decimal  |
+-------------+----------+
(student_id, course_id, semester) is the primary key (combination of columns with unique values) for this table.
Each row contains the student ID, course ID, semester, and grade received.

Write a solution to find the students who meet the following criteria:

Havetaken all mandatory courses and at least two elective courses offered in their major.
Achieved a grade of A in all mandatory courses and at least B inelective courses.
Maintained an average GPA of at least 2.5 across all their courses (including those outside their major).

Return the result table ordered by student_id inascending order.

Example 1:

 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


Input:
students table:
+------------+------------------+------------------+
| student_id | name             | major            |
+------------+------------------+------------------+
| 1          | Alice            | Computer Science |
| 2          | Bob              | Computer Science |
| 3          | Charlie          | Mathematics      |
| 4          | David            | Mathematics      |
+------------+------------------+------------------+
courses table:
+-----------+-------------------+---------+------------------+----------+
| course_id | name              | credits | major            | mandatory|
+-----------+-------------------+---------+------------------+----------+
| 101       | Algorithms        | 3       | Computer Science | yes      |
| 102       | Data Structures   | 3       | Computer Science | yes      |
| 103       | Calculus          | 4       | Mathematics      | yes      |
| 104       | Linear Algebra    | 4       | Mathematics      | yes      |
| 105       | Machine Learning  | 3       | Computer Science | no       |
| 106       | Probability       | 3       | Mathematics      | no       |
| 107       | Operating Systems | 3       | Computer Science | no       |
| 108       | Statistics        | 3       | Mathematics      | no       |
+-----------+-------------------+---------+------------------+----------+
enrollments table:
+------------+-----------+-------------+-------+-----+
| student_id | course_id | semester    | grade | GPA |
+------------+-----------+-------------+-------+-----+
| 1          | 101       | Fall 2023   | A     | 4.0 |
| 1          | 102       | Spring 2023 | A     | 4.0 |
| 1          | 105       | Spring 2023 | A     | 4.0 |
| 1          | 107       | Fall 2023   | B     | 3.5 |
| 2          | 101       | Fall 2023   | A     | 4.0 |
| 2          | 102       | Spring 2023 | B     | 3.0 |
| 3          | 103       | Fall 2023   | A     | 4.0 |
| 3          | 104       | Spring 2023 | A     | 4.0 |
| 3          | 106       | Spring 2023 | A     | 4.0 |
| 3          | 108       | Fall 2023   | B     | 3.5 |
| 4          | 103       | Fall 2023   | B     | 3.0 |
| 4          | 104       | Spring 2023 | B     | 3.0 |
+------------+-----------+-------------+-------+-----+
Output:
+------------+
| student_id |
+------------+
| 1          |
| 3          |
+------------+
Explanation:
* Alice (student_id 1) is a Computer Science major and has taken both Algorithms and Data Structures, receiving an A in both. She has also taken Machine Learning and Operating Systems as electives, receiving an A and B respectively.
* Bob (student_id 2) is a Computer Science major but did not receive an A in all required courses.
* Charlie (student_id 3) is a Mathematics major and has taken both Calculus and Linear Algebra, receiving an A in both. He has also taken Probability and Statistics as electives, receiving an A and B respectively.
* David (student_id 4) is a Mathematics major but did not receive an A in all required courses.
**Note:** Output table is ordered by student_id in ascending order.

Solution

Method 1 – Relational Division and Aggregation

Intuition

The key idea is to check, for each student:

Have they taken all mandatory courses in their major and scored ‘A’ in each?
Have they taken at least two elective courses in their major and scored at least ‘B’ in each?
Is their average GPA across all courses at least 2.5?

We use joins and groupings to check these conditions.

Approach

For each student, get their major.
Find all mandatory and elective courses for that major.
For each student, check:
- They have enrolled in all mandatory courses for their major and scored ‘A’ in each.
- They have enrolled in at least two elective courses for their major and scored at least ‘B’ in each.
- Their average GPA across all enrollments is at least 2.5.
Return the student_ids that satisfy all conditions, ordered by student_id.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


SELECT s.student_id
FROM students s
JOIN enrollments e ON s.student_id = e.student_id
JOIN courses c ON e.course_id = c.course_id AND c.major = s.major
GROUP BY s.student_id
HAVING
  SUM(c.mandatory = 'yes') = (
    SELECT COUNT(*) FROM courses WHERE major = s.major AND mandatory = 'yes'
  )
  AND SUM(c.mandatory = 'yes' AND e.grade = 'A') = (
    SELECT COUNT(*) FROM courses WHERE major = s.major AND mandatory = 'yes'
  )
  AND SUM(c.mandatory = 'no' AND (e.grade = 'A' OR e.grade = 'B')) >= 2
  AND (
    SELECT AVG(e2.GPA)
    FROM enrollments e2
    WHERE e2.student_id = s.student_id
  ) >= 2.5
ORDER BY s.student_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


SELECT s.student_id
FROM students s
JOIN enrollments e ON s.student_id = e.student_id
JOIN courses c ON e.course_id = c.course_id AND c.major = s.major
GROUP BY s.student_id
HAVING
  SUM(CASE WHEN c.mandatory = 'yes' THEN 1 ELSE 0 END) = (
    SELECT COUNT(*) FROM courses WHERE major = s.major AND mandatory = 'yes'
  )
  AND SUM(CASE WHEN c.mandatory = 'yes' AND e.grade = 'A' THEN 1 ELSE 0 END) = (
    SELECT COUNT(*) FROM courses WHERE major = s.major AND mandatory = 'yes'
  )
  AND SUM(CASE WHEN c.mandatory = 'no' AND (e.grade = 'A' OR e.grade = 'B') THEN 1 ELSE 0 END) >= 2
  AND (
    SELECT AVG(e2.GPA::float)
    FROM enrollments e2
    WHERE e2.student_id = s.student_id
  ) >= 2.5
ORDER BY s.student_id;

 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


class Solution:
    def find_top_students(
        self,
        students: 'pd.DataFrame',
        courses: 'pd.DataFrame',
        enrollments: 'pd.DataFrame'
    ) -> 'pd.DataFrame':
        ans = []
        for _, stu in students.iterrows():
            sid, major = stu['student_id'], stu['major']
            mand = courses[(courses['major'] == major) & (courses['mandatory'] == 'yes')]
            elect = courses[(courses['major'] == major) & (courses['mandatory'] == 'no')]
            stu_enr = enrollments[enrollments['student_id'] == sid]
            # Check all mandatory courses taken with 'A'
            mand_ids = set(mand['course_id'])
            mand_taken = stu_enr[stu_enr['course_id'].isin(mand_ids) & (stu_enr['grade'] == 'A')]
            if len(mand_taken) != len(mand_ids):
                continue
            # At least two electives with grade >= 'B'
            elect_ids = set(elect['course_id'])
            elect_taken = stu_enr[stu_enr['course_id'].isin(elect_ids) & (stu_enr['grade'].isin(['A', 'B']))]
            if len(elect_taken) < 2:
                continue
            # Average GPA >= 2.5
            if stu_enr['GPA'].mean() < 2.5:
                continue
            ans.append(sid)
        return pd.DataFrame({'student_id': sorted(ans)})

Complexity

⏰ Time complexity: O(N*M) where N is the number of students and M is the number of courses, since for each student we may check all courses in their major.
🧺 Space complexity: O(N) for storing the result list of qualifying students.

Problem#

Example 1:#

Solution#

Method 1 – Relational Division and Aggregation#

Intuition#

Approach#

Code#

Complexity#