LeetCode 1112 - Highest Grade For Each Student

The problem gives us a database table named Enrollments. Each row represents a student taking a course and receiving a grade for that course.

leetcodemediumdatabase

LeetCode Problem 1112

Difficulty: 🟡 Medium
Topics: Database

Solution

LeetCode 1112 - Highest Grade For Each Student

Problem Understanding

The problem gives us a database table named Enrollments. Each row represents a student taking a course and receiving a grade for that course.

The table has three columns:

Column Meaning
student_id The unique identifier of a student
course_id The unique identifier of a course
grade The student's grade in that course

The combination (student_id, course_id) is guaranteed to be unique, which means a student cannot appear more than once for the same course.

The task is to find, for every student, the course in which they achieved their highest grade. The output should contain:

  • student_id
  • course_id
  • grade

There is an important tie-breaking rule. If a student has multiple courses with the same highest grade, we must choose the course with the smallest course_id.

Finally, the result must be ordered by student_id in ascending order.

The problem is fundamentally a grouped maximum query with tie-breaking logic. We are grouping rows by student_id, finding the maximum grade within each group, and then resolving ties using the minimum course ID.

Several edge cases are important:

  • A student may have only one course.
  • A student may have multiple courses with the same highest grade.
  • Grades are guaranteed to be non-null.
  • Multiple students may share identical grades, but comparisons are always done independently per student.
  • The smallest course_id rule is easy to forget and can lead to incorrect results if not handled carefully.

Approaches

Brute Force Approach

A straightforward solution is to process each student independently.

For every student, we can scan all enrollment rows and track:

  • the highest grade seen so far
  • the course associated with that grade

Whenever we encounter:

  • a larger grade, we update the answer
  • an equal grade with a smaller course_id, we also update the answer

This approach is correct because every row belonging to the student is examined, guaranteeing that the best valid course is eventually selected.

However, if implemented naively, this can become inefficient. Suppose there are n rows and m students. Re-scanning the entire table for every student leads to O(n * m) time complexity, which is unnecessarily expensive.

Optimal Approach

The key observation is that we can solve the problem in a single grouped pass.

For each student, we only need to maintain the current best enrollment:

  • highest grade
  • smallest course ID in case of ties

This means we can process every row exactly once while maintaining a hash map keyed by student_id.

For each enrollment:

  • if the grade is higher than the stored best grade, replace the stored result
  • if the grade is equal and the course ID is smaller, replace the stored result
  • otherwise, ignore the row

This reduces the complexity to linear time.

In SQL, this problem is commonly solved using window functions such as ROW_NUMBER() with custom ordering rules.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(m) Repeatedly scans enrollments for each student
Optimal O(n) O(m) Single pass using grouping or ranking

Algorithm Walkthrough

Optimal SQL Algorithm Using Window Functions

  1. Partition the rows by student_id.

This groups together all enrollments belonging to the same student so they can be ranked independently. 2. Within each student partition, sort rows by:

  • grade in descending order
  • course_id in ascending order

Sorting this way guarantees that:

  • the highest grade appears first
  • ties are resolved by the smallest course ID
  1. Use ROW_NUMBER() to assign a ranking to each row inside the partition.

The best course for each student will receive rank 1. 4. Select only rows where row_number = 1.

These rows represent the final answer for each student. 5. Order the final output by student_id.

Why it works

The ordering criteria enforce the exact priority rules required by the problem:

  • larger grades are preferred
  • for equal grades, smaller course IDs are preferred

Because ROW_NUMBER() assigns rank 1 to the first row after sorting, the selected row is guaranteed to be the correct answer for that student.

Python Solution

Although this is a database problem, LeetCode database explanations often benefit from showing equivalent algorithmic logic. The following Python solution demonstrates the same idea programmatically.

from typing import List, Tuple

class Solution:
    def highestGrade(self, enrollments: List[Tuple[int, int, int]]) -> List[Tuple[int, int, int]]:
        best = {}

        for student_id, course_id, grade in enrollments:
            if student_id not in best:
                best[student_id] = (course_id, grade)
                continue

            current_course, current_grade = best[student_id]

            if grade > current_grade:
                best[student_id] = (course_id, grade)
            elif grade == current_grade and course_id < current_course:
                best[student_id] = (course_id, grade)

        result = []

        for student_id in sorted(best.keys()):
            course_id, grade = best[student_id]
            result.append((student_id, course_id, grade))

        return result

The implementation uses a dictionary named best where:

  • the key is student_id
  • the value stores the current best (course_id, grade)

As each enrollment is processed, the algorithm compares it against the stored best result for that student.

If the new grade is larger, the stored result is replaced.

If the grades are equal, the algorithm checks the tie-breaking rule and keeps the smaller course ID.

After processing all rows, the results are sorted by student ID and returned.

Go Solution

package main

import (
	"sort"
)

type Enrollment struct {
	StudentID int
	CourseID  int
	Grade     int
}

func highestGrade(enrollments []Enrollment) []Enrollment {
	best := make(map[int]Enrollment)

	for _, enrollment := range enrollments {
		current, exists := best[enrollment.StudentID]

		if !exists {
			best[enrollment.StudentID] = enrollment
			continue
		}

		if enrollment.Grade > current.Grade {
			best[enrollment.StudentID] = enrollment
		} else if enrollment.Grade == current.Grade &&
			enrollment.CourseID < current.CourseID {
			best[enrollment.StudentID] = enrollment
		}
	}

	studentIDs := make([]int, 0, len(best))

	for studentID := range best {
		studentIDs = append(studentIDs, studentID)
	}

	sort.Ints(studentIDs)

	result := make([]Enrollment, 0, len(studentIDs))

	for _, studentID := range studentIDs {
		result = append(result, best[studentID])
	}

	return result
}

The Go implementation follows the same logic as the Python version.

A map is used to store the best enrollment per student. Go requires explicit existence checks when reading from maps, so the code uses the exists boolean.

The final output order is achieved by extracting student IDs into a slice and sorting them before building the result.

Since all values are integers and constraints are small, integer overflow is not a concern here.

Worked Examples

Example 1

Input:

student_id course_id grade
2 2 95
2 3 95
1 1 90
1 2 99
3 1 80
3 2 75
3 3 82

Step-by-step processing

Initial state:

best = {}

Process (2, 2, 95):

best = {
    2: (2, 95)
}

Process (2, 3, 95):

  • Same grade as current best
  • Current best course ID is smaller
  • Keep existing result
best = {
    2: (2, 95)
}

Process (1, 1, 90):

best = {
    2: (2, 95),
    1: (1, 90)
}

Process (1, 2, 99):

  • Higher grade than 90
  • Replace result
best = {
    2: (2, 95),
    1: (2, 99)
}

Process (3, 1, 80):

best = {
    2: (2, 95),
    1: (2, 99),
    3: (1, 80)
}

Process (3, 2, 75):

  • Lower grade
  • Ignore
best = {
    2: (2, 95),
    1: (2, 99),
    3: (1, 80)
}

Process (3, 3, 82):

  • Higher grade than 80
  • Replace result
best = {
    2: (2, 95),
    1: (2, 99),
    3: (3, 82)
}

Final sorted output:

student_id course_id grade
1 2 99
2 2 95
3 3 82

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each enrollment row is processed exactly once
Space O(m) One stored result per student

The algorithm performs a constant amount of work for every enrollment row, leading to linear time complexity.

The extra space depends on the number of distinct students because the dictionary or hash map stores one best result per student.

Test Cases

from typing import List, Tuple

class Solution:
    def highestGrade(self, enrollments: List[Tuple[int, int, int]]) -> List[Tuple[int, int, int]]:
        best = {}

        for student_id, course_id, grade in enrollments:
            if student_id not in best:
                best[student_id] = (course_id, grade)
                continue

            current_course, current_grade = best[student_id]

            if grade > current_grade:
                best[student_id] = (course_id, grade)
            elif grade == current_grade and course_id < current_course:
                best[student_id] = (course_id, grade)

        result = []

        for student_id in sorted(best.keys()):
            course_id, grade = best[student_id]
            result.append((student_id, course_id, grade))

        return result

solution = Solution()

# Provided example
assert solution.highestGrade([
    (2, 2, 95),
    (2, 3, 95),
    (1, 1, 90),
    (1, 2, 99),
    (3, 1, 80),
    (3, 2, 75),
    (3, 3, 82)
]) == [
    (1, 2, 99),
    (2, 2, 95),
    (3, 3, 82)
]

# Single student, single course
assert solution.highestGrade([
    (1, 10, 88)
]) == [
    (1, 10, 88)
]

# Tie on grade, smaller course_id wins
assert solution.highestGrade([
    (1, 5, 90),
    (1, 2, 90),
    (1, 8, 90)
]) == [
    (1, 2, 90)
]

# Higher grade overrides smaller course_id
assert solution.highestGrade([
    (1, 1, 80),
    (1, 2, 95)
]) == [
    (1, 2, 95)
]

# Multiple students
assert solution.highestGrade([
    (3, 1, 70),
    (2, 2, 85),
    (1, 3, 92)
]) == [
    (1, 3, 92),
    (2, 2, 85),
    (3, 1, 70)
]

# Multiple tie situations
assert solution.highestGrade([
    (1, 3, 100),
    (1, 1, 100),
    (2, 2, 95),
    (2, 1, 95)
]) == [
    (1, 1, 100),
    (2, 1, 95)
]
Test Why
Provided example Validates normal mixed behavior
Single student, single course Smallest valid input
Tie on grade Verifies tie-breaking rule
Higher grade overrides smaller course ID Ensures grade priority is correct
Multiple students Confirms sorting by student ID
Multiple tie situations Tests repeated tie resolution logic

Edge Cases

One important edge case occurs when a student has only one enrollment. A buggy implementation might assume multiple rows exist per student and accidentally skip such students. This implementation correctly initializes the student's best result the first time the student appears.

Another important case is when multiple courses share the same highest grade. Without explicit tie-breaking logic, the selected course may depend on iteration order, which is incorrect. The implementation handles this by explicitly choosing the smaller course_id whenever grades are equal.

A third edge case occurs when enrollments are not sorted by student or grade. Some incorrect solutions assume rows arrive in a helpful order. This implementation does not rely on ordering at all because every row is independently compared against the current best result.

A subtle bug source is replacing results too aggressively. For example, if a student already has grade 95 in course 2, encountering another 95 in course 5 should not replace the answer. The implementation carefully checks both conditions before updating stored values.