LeetCode 2989 - Class Performance

LeetCode Problem 2989

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem asks us to calculate the difference between the highest and lowest total scores among students in a class. Each student has three assignment scores, and the total score is simply the sum of these three values. The input is a database table named Scores with columns student_id, student_name, assignment1, assignment2, and assignment3. Each student_id is unique, ensuring no duplicates.

The expected output is a single-row table with one column, difference_in_score, which contains the difference between the maximum total score and the minimum total score across all students. There is no requirement to sort the result since it is a single value.

Constraints and guarantees implied by the problem include that each score is an integer and that at least one student exists (otherwise computing a difference would be meaningless). Important edge cases include all students having the same total score, which would result in a difference of zero, or having negative scores, although the example uses only positive integers.

Approaches

The brute-force approach would calculate the total score for each student individually and then store all totals in a list or temporary table. Afterward, one would compute the maximum and minimum of these totals and return their difference. This works correctly but involves unnecessary storage of all totals when we only need the maximum and minimum, which can be tracked incrementally.

The optimal approach leverages SQL aggregation functions directly. By summing each student's three assignments in a subquery, we can then apply MAX and MIN directly on these sums without storing intermediate results. This reduces storage overhead and is more idiomatic SQL.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Compute total per student, store all totals, then compute max-min
Optimal	O(n)	O(1)	Use SQL aggregation functions MAX and MIN directly on sums

Algorithm Walkthrough

1. Compute the total score for each student by summing assignment1, assignment2, and assignment3. This can be done in a subquery or inline.
2. Apply the MAX() function to find the highest total score.
3. Apply the MIN() function to find the lowest total score.
4. Subtract the minimum total score from the maximum total score.
5. Return the result as a single-row table with column name difference_in_score.

Why it works: The algorithm guarantees correctness because MAX() and MIN() will always return the extreme values from a set of numbers. Summing the three assignments for each student ensures we are comparing total scores, which matches the problem requirement.

Python Solution

import sqlite3
from typing import List, Tuple

def class_performance_difference(cursor: sqlite3.Cursor) -> List[Tuple[int]]:
    query = """
    SELECT MAX(total_score) - MIN(total_score) AS difference_in_score
    FROM (
        SELECT assignment1 + assignment2 + assignment3 AS total_score
        FROM Scores
    ) AS student_totals;
    """
    cursor.execute(query)
    return cursor.fetchall()

This Python solution uses a SQLite cursor to execute a query. First, it calculates total_score for each student in a subquery. Then, MAX and MIN aggregate functions are applied to compute the difference, returning a single-row result.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "fmt"
)

func ClassPerformanceDifference(db *sql.DB) (int, error) {
    query := `
    SELECT MAX(total_score) - MIN(total_score) AS difference_in_score
    FROM (
        SELECT assignment1 + assignment2 + assignment3 AS total_score
        FROM Scores
    ) AS student_totals;
    `
    var difference int
    err := db.QueryRow(query).Scan(&difference)
    if err != nil {
        return 0, err
    }
    return difference, nil
}

func main() {
    db, _ := sql.Open("sqlite3", "./test.db")
    defer db.Close()
    diff, _ := ClassPerformanceDifference(db)
    fmt.Println(diff)
}

In Go, the approach is similar, using QueryRow to fetch a single integer value. The subquery sums the three assignments per student, and MAX-MIN computes the difference.

Worked Examples

For the example provided:

student_id	total_score
309	222
321	230
338	207
423	151
896	119
235	153

MAX(total_score) is 230 and MIN(total_score) is 119. Subtracting gives 230 - 119 = 111.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each student is visited once to compute the sum; aggregation functions scan all totals once
Space	O(1)	No additional storage required beyond intermediate aggregation

This is optimal for SQL as aggregation functions operate in constant memory relative to the number of rows.

Test Cases

# test cases
import sqlite3

conn = sqlite3.connect(':memory:')
c = conn.cursor()
c.execute('''CREATE TABLE Scores(
    student_id INT, 
    student_name VARCHAR, 
    assignment1 INT, 
    assignment2 INT, 
    assignment3 INT
)''')

# Example test
students = [
    (309, "Owen", 88, 47, 87),
    (321, "Claire", 98, 95, 37),
    (338, "Julian", 100, 64, 43),
    (423, "Peyton", 60, 44, 47),
    (896, "David", 32, 37, 50),
    (235, "Camila", 31, 53, 69)
]
c.executemany("INSERT INTO Scores VALUES (?,?,?,?,?)", students)
assert class_performance_difference(c)[0][0] == 111  # Provided example

# Edge case: all same total
c.execute("DELETE FROM Scores")
students_same = [
    (1, "A", 10,10,10),
    (2, "B", 10,10,10)
]
c.executemany("INSERT INTO Scores VALUES (?,?,?,?,?)", students_same)
assert class_performance_difference(c)[0][0] == 0  # Difference is zero

# Edge case: single student
c.execute("DELETE FROM Scores")
c.execute("INSERT INTO Scores VALUES (1,'Solo',100,100,100)")
assert class_performance_difference(c)[0][0] == 0  # Difference is zero

Test	Why
Provided example	Validates typical input with varying totals
All students same	Ensures difference calculation handles zero correctly
Single student	Ensures algorithm works with minimal input

Edge Cases

The first edge case is all students having identical scores, which could produce a difference of zero. The solution handles this automatically because MAX and MIN will be equal, giving a difference of zero.

The second edge case is a single student in the table. The difference should also be zero because the maximum and minimum total scores are the same. Our algorithm naturally supports this case without modification.

The third edge case is large numbers for assignment scores. Summing large integers could risk overflow in some languages, but in Python this is handled natively with arbitrary-length integers, and in SQL or Go, integers are typically sufficient for reasonable assignment scores. If extreme values were possible, using BIGINT would be advisable.

This solution comprehensively handles normal, minimal, and maximal inputs safely and efficiently.