LeetCode 1412 - Find the Quiet Students in All Exams

LeetCode Problem 1412

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This problem asks us to identify students who are "quiet" across all exams they participated in. A student is considered quiet if, in every exam they took, they never achieved either the highest score or the lowest score.

We are given two tables:

• The Student table contains student IDs and names.
• The Exam table records exam participation and scores.

Each row in the Exam table represents one student's score in one specific exam. Multiple students can belong to the same exam.

The important detail is that we are not looking for students who were quiet in at least one exam. Instead, we want students who were quiet in every exam they took.

For each exam:

• Any student with the maximum score is disqualified.
• Any student with the minimum score is disqualified.
• If a student ever appears in either category, they cannot be part of the final result.

The final answer should include:

• Students who took at least one exam
• Students who were never the highest scorer
• Students who were never the lowest scorer

The output must be ordered by student_id.

Consider the sample carefully:

• Student 1 repeatedly receives the minimum score.
• Student 3 and Student 4 receive maximum scores.
• Student 2 participates and never becomes highest or lowest.
• Student 5 never takes an exam.

Therefore:

• Student 2 is included.
• Student 5 is excluded because the problem explicitly says students with no exams should not appear.

Several edge cases are important here.

If an exam has only one participant, that student is simultaneously both highest and lowest, meaning they are immediately disqualified.

If multiple students tie for the highest or lowest score, every tied student is considered non-quiet and must be excluded.

A student may participate in many exams and only need to fail once to become invalid.

The problem is fundamentally about filtering students based on aggregate exam behavior.

Approaches

Brute Force Approach

A straightforward solution is to process each student independently.

For every student:

1. Find all exams they participated in.
2. For each of those exams:

• Compute the minimum score
• Compute the maximum score
• Compare the student's score against those values

3. If the student's score ever equals either extreme, mark them as non-quiet.

This works because it directly follows the problem definition. However, it is inefficient because minimum and maximum scores for the same exam are recomputed repeatedly for different students.

Suppose an exam contains 1000 students. If we recompute min/max for every participant independently, we repeatedly scan the same data many times.

This creates unnecessary repeated work and leads to poor scalability.

Optimal Approach

The key observation is that exam-level information should be computed once.

For every exam:

• Determine the minimum score
• Determine the maximum score
• Mark all students who match either boundary score as disqualified

After processing all exams:

• Collect students who participated in at least one exam
• Exclude all disqualified students
• Return the remaining students

This approach is efficient because:

• Each exam is analyzed once
• Each row is processed a constant number of times
• We use set-based filtering instead of repeated rescanning

In SQL, this maps naturally to:

• Window functions or aggregation
• A set of disqualified students
• Final filtering using NOT IN or joins

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(S × E)	O(1)	Recomputes min/max repeatedly for each student
Optimal	O(E)	O(E)	Computes exam boundaries once and filters efficiently

Here:

• S is the number of students
• E is the number of exam rows

Algorithm Walkthrough

Using SQL Aggregation and Filtering

1. First, compute the minimum and maximum score for every exam.

We group rows by exam_id and calculate:

• MIN(score)
• MAX(score)

This gives us the score boundaries for each exam. 2. Next, identify students who are not quiet.

We join the original Exam table with the exam statistics and check:

• score = min_score
• score = max_score

Any matching student becomes disqualified. 3. Store all disqualified student IDs.

A student only needs one bad exam to become invalid, so we use DISTINCT to avoid duplicates. 4. Identify students who actually participated in exams.

The problem explicitly excludes students who never took an exam. 5. Join with the Student table.

This allows us to retrieve student names. 6. Exclude all disqualified students.

We keep only students whose IDs are not present in the disqualified set. 7. Sort the final output by student_id.

Why it works

The algorithm works because every exam independently defines a set of invalid students:

• students with minimum scores
• students with maximum scores

A quiet student must avoid both categories in every exam they take.

By collecting the union of all invalid students and excluding them from participating students, we exactly capture the required definition.

Python Solution

Although this is a Database problem, the following Python implementation demonstrates the same logic algorithmically.

from collections import defaultdict
from typing import List

class Solution:
    def quietStudents(
        self,
        students: List[List],
        exams: List[List[int]]
    ) -> List[List]:
        
        exam_scores = defaultdict(list)

        for exam_id, student_id, score in exams:
            exam_scores[exam_id].append((student_id, score))

        disqualified = set()
        participated = set()

        for exam_id, entries in exam_scores.items():
            scores = [score for _, score in entries]

            min_score = min(scores)
            max_score = max(scores)

            for student_id, score in entries:
                participated.add(student_id)

                if score == min_score or score == max_score:
                    disqualified.add(student_id)

        result = []

        for student_id, student_name in students:
            if (
                student_id in participated
                and student_id not in disqualified
            ):
                result.append([student_id, student_name])

        result.sort(key=lambda x: x[0])

        return result

The implementation begins by grouping exam records by exam_id. This allows us to process each exam independently.

For every exam, we compute:

• the minimum score
• the maximum score

We then iterate through all participants in that exam. Any student whose score matches either boundary becomes disqualified.

At the same time, we track which students participated in at least one exam.

Finally, we iterate through the student list and keep only students who:

• participated in exams
• never appeared in the disqualified set

The result is sorted before returning.

Go Solution

package main

import (
	"sort"
)

type Student struct {
	ID   int
	Name string
}

func quietStudents(
	students []Student,
	exams [][]int,
) [][]interface{} {

	examScores := make(map[int][][]int)

	for _, exam := range exams {
		examID := exam[0]
		studentID := exam[1]
		score := exam[2]

		examScores[examID] = append(
			examScores[examID],
			[]int{studentID, score},
		)
	}

	disqualified := make(map[int]bool)
	participated := make(map[int]bool)

	for _, entries := range examScores {

		minScore := entries[0][1]
		maxScore := entries[0][1]

		for _, entry := range entries {
			score := entry[1]

			if score < minScore {
				minScore = score
			}

			if score > maxScore {
				maxScore = score
			}
		}

		for _, entry := range entries {
			studentID := entry[0]
			score := entry[1]

			participated[studentID] = true

			if score == minScore || score == maxScore {
				disqualified[studentID] = true
			}
		}
	}

	result := [][]interface{}{}

	for _, student := range students {
		if participated[student.ID] &&
			!disqualified[student.ID] {

			result = append(result, []interface{}{
				student.ID,
				student.Name,
			})
		}
	}

	sort.Slice(result, func(i, j int) bool {
		return result[i][0].(int) < result[j][0].(int)
	})

	return result
}

The Go implementation follows the same overall structure as the Python version.

Because Go does not have Python's flexible tuple support, we represent exam entries using nested integer slices.

We use maps as hash sets:

• map[int]bool for disqualified students
• map[int]bool for participation tracking

Sorting requires sort.Slice with a custom comparator.

Unlike Python, Go requires explicit initialization and type handling, especially when storing mixed output values in [][]interface{}.

SQL Solution

WITH exam_stats AS (
    SELECT
        exam_id,
        MIN(score) AS min_score,
        MAX(score) AS max_score
    FROM Exam
    GROUP BY exam_id
),
disqualified AS (
    SELECT DISTINCT e.student_id
    FROM Exam e
    JOIN exam_stats s
        ON e.exam_id = s.exam_id
    WHERE e.score = s.min_score
       OR e.score = s.max_score
)

SELECT
    s.student_id,
    s.student_name
FROM Student s
JOIN Exam e
    ON s.student_id = e.student_id
WHERE s.student_id NOT IN (
    SELECT student_id
    FROM disqualified
)
GROUP BY s.student_id, s.student_name
ORDER BY s.student_id;

This SQL solution first computes exam boundaries using aggregation.

The disqualified CTE collects every student who ever received either the minimum or maximum score in any exam.

The final query:

• joins students with exams to ensure participation
• excludes disqualified students
• groups duplicates caused by joins
• orders results by student ID

Worked Examples

Example 1

Input:

Student table:

student_id	student_name
1	Daniel
2	Jade
3	Stella
4	Jonathan
5	Will

Exam table:

exam_id	student_id	score
10	1	70
10	2	80
10	3	90
20	1	80
30	1	70
30	3	80
30	4	90
40	1	60
40	2	70
40	4	80

Step 1: Group exams

exam_id	Entries
10	(1,70), (2,80), (3,90)
20	(1,80)
30	(1,70), (3,80), (4,90)
40	(1,60), (2,70), (4,80)

Step 2: Process exam 10

Scores:

• Minimum = 70
• Maximum = 90

Disqualified students:

• Student 1
• Student 3

Current sets:

Set	Values
participated	{1,2,3}
disqualified	{1,3}

Step 3: Process exam 20

Only one participant:

• Minimum = 80
• Maximum = 80

Student 1 is both minimum and maximum.

Set	Values
participated	{1,2,3}
disqualified	{1,3}

Step 4: Process exam 30

Scores:

• Minimum = 70
• Maximum = 90

Disqualified:

• Student 1
• Student 4

Set	Values
participated	{1,2,3,4}
disqualified	{1,3,4}

Step 5: Process exam 40

Scores:

• Minimum = 60
• Maximum = 80

Disqualified:

• Student 1
• Student 4

Final sets:

Set	Values
participated	{1,2,3,4}
disqualified	{1,3,4}

Step 6: Build answer

Check each student:

Student	Participated	Disqualified	Result
1	Yes	Yes	Exclude
2	Yes	No	Include
3	Yes	Yes	Exclude
4	Yes	Yes	Exclude
5	No	No	Exclude

Final answer:

student_id	student_name
2	Jade

Complexity Analysis

Measure	Complexity	Explanation
Time	O(E)	Each exam row is processed a constant number of times
Space	O(E)	Hash maps and grouping structures may store all exam rows

The dominant cost comes from grouping exam records and scanning them to determine minimum and maximum values.

Each exam row participates in:

• grouping
• min/max calculation
• qualification checking

No nested rescanning occurs in the optimal approach, so the total runtime remains linear relative to the number of exam records.

Test Cases

from collections import defaultdict

class Solution:
    def quietStudents(self, students, exams):

        exam_scores = defaultdict(list)

        for exam_id, student_id, score in exams:
            exam_scores[exam_id].append((student_id, score))

        disqualified = set()
        participated = set()

        for entries in exam_scores.values():

            scores = [score for _, score in entries]

            min_score = min(scores)
            max_score = max(scores)

            for student_id, score in entries:
                participated.add(student_id)

                if score == min_score or score == max_score:
                    disqualified.add(student_id)

        result = []

        for student_id, student_name in students:
            if (
                student_id in participated
                and student_id not in disqualified
            ):
                result.append([student_id, student_name])

        result.sort()

        return result

solver = Solution()

# Provided example
students = [
    [1, "Daniel"],
    [2, "Jade"],
    [3, "Stella"],
    [4, "Jonathan"],
    [5, "Will"]
]

exams = [
    [10, 1, 70],
    [10, 2, 80],
    [10, 3, 90],
    [20, 1, 80],
    [30, 1, 70],
    [30, 3, 80],
    [30, 4, 90],
    [40, 1, 60],
    [40, 2, 70],
    [40, 4, 80]
]

assert solver.quietStudents(students, exams) == [
    [2, "Jade"]
]  # Standard example

# Single student in one exam
students = [
    [1, "Alice"]
]

exams = [
    [1, 1, 100]
]

assert solver.quietStudents(students, exams) == []  
# Single participant is both min and max

# Two students tied for highest
students = [
    [1, "A"],
    [2, "B"],
    [3, "C"]
]

exams = [
    [1, 1, 50],
    [1, 2, 100],
    [1, 3, 100]
]

assert solver.quietStudents(students, exams) == []  
# Students 2 and 3 are max, student 1 is min

# Student participates quietly in all exams
students = [
    [1, "A"],
    [2, "B"],
    [3, "C"]
]

exams = [
    [1, 1, 10],
    [1, 2, 20],
    [1, 3, 30],
    [2, 1, 15],
    [2, 2, 20],
    [2, 3, 25]
]

assert solver.quietStudents(students, exams) == [
    [2, "B"]
]  # Student 2 is always middle

# Student never participates
students = [
    [1, "A"],
    [2, "B"]
]

exams = [
    [1, 1, 100]
]

assert solver.quietStudents(students, exams) == []  
# Student 2 excluded because no participation

# Multiple quiet students
students = [
    [1, "A"],
    [2, "B"],
    [3, "C"],
    [4, "D"]
]

exams = [
    [1, 1, 10],
    [1, 2, 20],
    [1, 3, 30],
    [1, 4, 25]
]

assert solver.quietStudents(students, exams) == [
    [2, "B"],
    [4, "D"]
]  # Middle scores remain valid

Test	Why
Provided example	Validates the core logic
Single student exam	Ensures one participant becomes both min and max
Tied highest scores	Confirms all tied extremes are disqualified
Consistently middle student	Verifies correct quiet student detection
Non-participating student	Ensures inactive students are excluded
Multiple quiet students	Confirms multiple valid outputs are handled

Edge Cases

Exam with only one participant

An exam containing a single student is tricky because that student is simultaneously both the minimum and maximum scorer.

A naive implementation might incorrectly assume a student cannot be both.

Our implementation correctly handles this because the condition checks:

score == min_score or score == max_score

When both values are identical, the student is still disqualified.

Multiple students tied for highest or lowest

Some implementations incorrectly assume only one student can hold the minimum or maximum score.

However, ties are possible and every tied student must be excluded.

Our algorithm scans every participant and compares scores directly against the computed boundaries, ensuring all tied students are disqualified.

Students who never take exams

It is easy to accidentally include students who never participated because they also never became highest or lowest.

The problem explicitly excludes them.

Our implementation uses a participated set and only includes students present in that set, guaranteeing correct behavior.