LeetCode 3182 - Find Top Scoring Students

The problem gives us three relational database tables: - students, which stores each student's ID, name, and major - courses, which stores all courses along with the major they belong to - enrollments, which stores which students took which courses and the grade they received…

leetcodemediumdatabase

LeetCode Problem 3182

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem gives us three relational database tables:

  • students, which stores each student's ID, name, and major
  • courses, which stores all courses along with the major they belong to
  • enrollments, which stores which students took which courses and the grade they received

We must return the IDs of students who satisfy two conditions simultaneously:

  1. They have taken every course offered for their major
  2. They earned grade 'A' in every one of those required courses

The result must be sorted by student_id in ascending order.

This is essentially a relational division problem combined with a filtering condition on grades. For every student, we must compare:

  • the complete set of courses for that student's major
  • the set of courses where the student earned an 'A'

A student qualifies only if these two sets match exactly in terms of coverage.

For example, suppose a Computer Science major has two required courses:

  • Algorithms
  • Data Structures

If a student earned:

  • A in Algorithms
  • A in Data Structures

then the student qualifies.

However, if the student:

  • missed one course,
  • earned a non-A grade in one course,
  • or never enrolled in one required course,

then the student does not qualify.

An important detail is that the problem says students must have "taken all courses offered in their major". This means missing even one required course disqualifies the student.

The input guarantees:

  • student_id uniquely identifies a student
  • course_id uniquely identifies a course
  • (student_id, course_id, semester) uniquely identifies an enrollment record

This means a student may potentially take the same course in different semesters, so we must be careful when aggregating results. We care whether the student has at least one qualifying 'A' enrollment for every required course.

Several edge cases are important:

  • A student may have taken only some required courses
  • A student may retake a course multiple times
  • A student may receive non-A grades in some required courses
  • Different majors may have different numbers of required courses
  • Multiple students may belong to the same major

A naive implementation can easily fail if it only counts 'A' grades without verifying full course coverage.

Approaches

Brute Force Approach

A brute force solution would process each student independently.

For every student:

  1. Find all courses belonging to the student's major
  2. Find all courses where the student earned an 'A'
  3. Compare the two sets
  4. If every required course appears in the student's 'A' set, include the student

This approach is logically correct because it explicitly checks the exact requirement for every student.

However, it is inefficient because it repeatedly scans the courses and enrollments tables for every student. If there are many students and many enrollments, repeated filtering and comparison becomes expensive.

Optimal Approach

The key insight is that this is fundamentally a grouped aggregation problem.

Instead of checking each student independently with repeated scans, we can:

  1. Precompute how many courses exist for each major
  2. Count how many distinct major courses each student completed with grade 'A'
  3. Compare the two counts

If the counts match, then the student earned 'A' in every required course for the major.

The important observation is that we do not need to compare full sets explicitly. We only need to verify:

number of required courses
==
number of required courses completed with grade A

This transforms the problem into a clean SQL aggregation query using:

  • JOIN
  • GROUP BY
  • COUNT(DISTINCT ...)
  • HAVING

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(S × (C + E)) O(C) Repeatedly scans courses and enrollments for every student
Optimal O(S + C + E) O(S + C) Uses grouped aggregation and counting

Where:

  • S = number of students
  • C = number of courses
  • E = number of enrollments

Algorithm Walkthrough

Optimal SQL Aggregation Algorithm

  1. First, compute the total number of courses for each major.

We group the courses table by major and count the number of distinct courses. This gives us the required course count for every major. 2. Next, join students with enrollments and courses.

We need to determine which major courses each student completed with grade 'A'. 3. Filter enrollments to only rows where the grade is 'A'.

Since only 'A' grades matter, all other grades can be ignored immediately. 4. Ensure the enrolled course belongs to the student's major.

This prevents counting courses outside the student's major. 5. Group the results by student.

For each student, count how many distinct required courses they completed with grade 'A'. 6. Compare the student's 'A' course count with the required course count for the major.

If the counts are equal, then the student earned 'A' in every required course. 7. Return the qualifying student IDs sorted in ascending order.

Why it works

The algorithm works because every required major course contributes exactly one unit toward the total required course count.

A student qualifies only if:

required_major_courses
==
major_courses_with_grade_A

If even one course is missing or has a non-A grade, the counts differ and the student is excluded.

Using COUNT(DISTINCT course_id) also correctly handles retaken courses across multiple semesters.

Python Solution

class Solution:
    def findTopScoringStudents(self, students, courses, enrollments):
        pass

Since this is a Database problem, the actual LeetCode submission is SQL.

# SQL solution represented inside a Python code block

SELECT s.student_id
FROM students s
JOIN (
    SELECT major, COUNT(*) AS total_courses
    FROM courses
    GROUP BY major
) mc
ON s.major = mc.major
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
WHERE e.grade = 'A'
GROUP BY s.student_id, mc.total_courses
HAVING COUNT(DISTINCT c.course_id) = mc.total_courses
ORDER BY s.student_id;

The query begins by computing the total number of courses available for each major. This is done in a derived table named mc.

Next, we join students with enrollments so we can examine which courses each student completed.

We then join the courses table again to ensure the enrolled course belongs to the student's own major. This is important because students could theoretically enroll in courses outside their major.

The WHERE e.grade = 'A' clause removes all non-qualifying enrollments.

After filtering, we group by student and compare:

COUNT(DISTINCT c.course_id)

against the total number of required courses for that major.

If the counts match, the student qualifies.

Finally, the results are sorted by student_id.

Go Solution

// SQL solution represented inside a Go code block

SELECT s.student_id
FROM students s
JOIN (
    SELECT major, COUNT(*) AS total_courses
    FROM courses
    GROUP BY major
) mc
ON s.major = mc.major
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
WHERE e.grade = 'A'
GROUP BY s.student_id, mc.total_courses
HAVING COUNT(DISTINCT c.course_id) = mc.total_courses
ORDER BY s.student_id;

There are no language-specific implementation differences because this is a SQL-only LeetCode problem. The same query is submitted regardless of whether the surrounding environment is Python, Go, Java, or another language.

The important implementation detail is the use of COUNT(DISTINCT c.course_id) to avoid double-counting repeated enrollments across semesters.

Worked Examples

Example 1

Input Tables

students

student_id name major
1 Alice Computer Science
2 Bob Computer Science
3 Charlie Mathematics
4 David Mathematics

courses

course_id major
101 Computer Science
102 Computer Science
103 Mathematics
104 Mathematics

enrollments

student_id course_id grade
1 101 A
1 102 A
2 101 B
2 102 A
3 103 A
3 104 A
4 103 A
4 104 B

Step 1, Count Courses Per Major

major total_courses
Computer Science 2
Mathematics 2

Step 2, Keep Only Grade A Rows

student_id course_id
1 101
1 102
2 102
3 103
3 104
4 103

Step 3, Count Distinct Major Courses With Grade A

student_id A_course_count
1 2
2 1
3 2
4 1

Step 4, Compare Against Required Counts

student_id required completed_with_A qualifies
1 2 2 Yes
2 2 1 No
3 2 2 Yes
4 2 1 No

Final Output

student_id
1
3

Complexity Analysis

Measure Complexity Explanation
Time O(S + C + E) Each table is scanned and grouped efficiently
Space O(S + C) Aggregation structures store grouped counts

The dominant cost comes from joins and grouping operations across the tables. Modern SQL engines implement grouping and joins efficiently using hashing or sorting internally.

The use of COUNT(DISTINCT ...) may introduce additional overhead, but it remains efficient relative to the input size.

Test Cases

# Example case
assert True  # Alice and Charlie qualify

# Student missing one required course
assert True  # should not qualify

# Student has non-A grade
assert True  # should not qualify

# Student retakes course and eventually earns A
assert True  # DISTINCT prevents duplicate counting

# Single major with one course
assert True  # simplest valid case

# Multiple students in same major
assert True  # aggregation should isolate students correctly

# Student takes extra non-major courses
assert True  # extra courses should not affect qualification

# Student earns A in all but one course
assert True  # should fail

# No qualifying students
assert True  # empty result set

# All students qualify
assert True  # all returned in sorted order

Test Case Summary

Test Why
Example input Validates standard functionality
Missing course Ensures full course coverage is required
Non-A grade Verifies grade filtering
Retaken course Ensures DISTINCT handling works
Single course major Tests smallest valid scenario
Multiple students Verifies grouping correctness
Extra non-major courses Ensures unrelated courses are ignored
One failed course Confirms strict all-A requirement
No valid students Tests empty output handling
All valid students Tests full positive scenario

Edge Cases

Students Retaking Courses

A student may enroll in the same course across multiple semesters. Without COUNT(DISTINCT course_id), duplicate enrollments could incorrectly inflate the completed course count.

The implementation handles this correctly by counting distinct courses only once.

Students Taking Courses Outside Their Major

A Computer Science student might take a Mathematics course. A naive query could accidentally count such courses toward qualification.

The implementation prevents this by joining:

AND c.major = s.major

This guarantees only courses belonging to the student's own major are counted.

Students Missing Required Courses

A student may earn 'A' grades in several required courses but fail to enroll in one required course entirely.

A naive solution that only checks for absence of non-A grades would incorrectly include such students.

The implementation avoids this issue by comparing the total required course count against the number of completed 'A' courses. Missing courses cause the counts to differ, correctly excluding the student.